CodeChef : January Challenge 2017 – Reservior

By | January 14, 2017
Reservior

Source: CodeChef

You are given a structure of a water reservoir. The reservoir is a 2 dimensional structure of height N and width M. It can be thought of divided into M vertical sections, each of equal width. The reservoir height is of N blocks. Each block of the reservoir can contain either water, brick or air. We will denote the water by character ‘W’, brick by ‘B’ and air by ‘A’.

You are given representation of reservoir at a fixed instant. Can you tell whether the current state of reservoir is stable, i.e. it will remain on the same state forever or not?

For example, let the reservoir be

WW
BB

This is not stable, as the water in the block (1, 1) can overflow to the left, similarly water in block (1, 2) can overflow to the right too.

BWB
BBB

This is stable, as the water at block (1, 2) is entrapped between bricks from all sides.

AWA
BBB

This is not stable, as the water at block (1, 2) might overflow to the left or the right.

BAA
ABB

This is not stable, as there is a brick at block (1, 1) and air at (2, 1). The brick will go down and air will come up, so its not stable too.

BWAAB
BWBWB
BBBBB

This is not stable too, as there is water at block (1, 2) and air at (1, 3), and (1, 4). The water will move towards those blocks.

BBB
BAB
BBB

This is not stable too, as there is air at block (2, 2). So brick at (1, 2) will fill the gap made by air.

Now, you are given description of reservoir. Can you tell whether the current state of reservoir is stable or not?

Input

The first line of input contains an integer T denoting number of test cases. Description of T test cases follows.

The first line of each test case, contains two integers N and M denoting the height and width of reservoir, respectively.

Each of the next N lines a string of length M. The j-th character in the i-th of the line denotes content at block (i, j). The characters can be ‘B’ denoting brick, ‘A’ denoting air, ‘W’ denoting water.

Output

For each test case, output a line containing “yes” or “no” (without quotes) corresponding to the situation whether the reservoir is stable or not?

Constraints

  • 1T50
  • 1N, M1000

Subtask #1: (15 points)

  • There is no water in the reservoir.

Subtask #2: (25 points)

  • 1N, M100

Subtask #3: (60 points)

  • original constraints

Example

Input:
6
2 2
WW
BB
2 3
BWB
BBB
2 3
AWA
BBB
2 3
BAA
ABB
3 5
BWAAB
BWBWB
BBBBB
3 3
BBB
BAB
BBB

Output:
no
yes
no
no
no
no

Explanation

All the examples are explained in the problem statement itself.

Solution:

I have submitted the solution. It is passing 1 test case in each category.
Working to analyse all the possible scenarios.
I am checking top, down, left and right coordinates of all the values, 
which I have taken in 2d array.
For suggestions or hints, please comment.

My Code:

package januaryChallenge2017;

import java.util.Scanner;

public class Reservior {
	
	public static void main(String[] args) {
		
		Scanner scan= new Scanner(System.in);
		int t=scan.nextInt();
		
		for(int i=0;i<t;i++)
		{
			int row=scan.nextInt();
			int column=scan.nextInt();

			char a[][]= new char[row][column];
			
			scan.nextLine();
			
		for(int j=0;j<row;j++)
		{
			String lines = scan.nextLine();
			char pa[]=lines.toCharArray();
			int k=0;
			for (char cs : pa) {
				a[j][k]=cs;
				k++;
				}
				
		}
			
			int spill=0;
			int noWater=0;

			for(int j=0;j<row;j++)
			{
				if(spill==1)
					break;
				for(int k=0;k<column;k++)
				{
					int leftJ=0, leftK=0, rightJ=0, rightK=0, upJ=0, upK=0, downJ=0, downK=0;
					
					if(k==0)
					{
						leftJ=-1; leftK=-1;
					}
					else
					{
						leftJ=j; leftK=k-1;
					}
					if(j==0)
					{
						upJ=-1; upK=-1;
					}
					else
					{
						upJ=j-1; upK=k;
					}
					if(k==column-1)
					{
						rightJ=-1;
						rightK=-1;
					}
					else
					{
						rightJ=j;
						rightK=k+1;
					}
					if(j==row-1)
					{
						downJ=-1;
						downK=-1;
					}
					else
					{
						downJ=j+1; downK=k;
					}
					
					if(a[j][k]=='W' )						
						{
						noWater=1;
						
						if((leftJ==-1 && leftK==-1) || (rightJ==-1 && rightK==-1) || (downJ==-1 && downK== -1))
						{
						spill=1;
						break;
						}
						else if(a[leftJ][leftK]=='B' && a[rightJ][rightK]=='B' && a[downJ][downK]=='B')
							{
							spill=0;
							}
						
						else
						{
							//System.out.println("spill water");
							spill=1;
							break;
						}
						
						}
					
					else if(a[j][k]=='B')
					{
						if( downJ!=-1 && downK!=-1)
							{
								if(a[downJ][downK]=='W' || a[downJ][downK]=='A')
								{

									//System.out.println("spill brick");
									spill=1;
									break;
								}
																
							}
					}
					
			/*		System.out.println(" leftJ, leftK, rightJ, rightK, upJ, upK, downJ, downK"+  
					leftJ + leftK + rightJ + rightK + upJ + upK + downJ +  downK);
					Syst	em.out.println();*/
				}
			}
			
		/*	if(noWater==0)
				System.out.println("no");
			else*/ if(spill==1)
				System.out.println("no");
			else
				System.out.println("yes");
			
			
		}
		
	}

}