Farm land with cells Empty, Water and Barrier


  • 0
    R

    You are given a farm land of size MxN as input. The land is divided into "cells" and each cell can be of the type:

    W -> filled with water, E -> Empty, # -> barrier

    Eg:
    E E E
    E # W
    E W E

    Scenario: After every 1 hour, an empty "E" cell, with a water filled "W" neighbor (up/down/left/right) cell, gets filled with water as well. Barriers remain barrier, they don't change.

    After hour #1:

    E E W
    E # W
    W W W

    After hour #2:

    E W W
    W # W
    W W W

    After hour #3:

    W W W
    W # W
    W W W

    Question: How many hours does it take to fill all "fillable" empty cells to get filled with water.
    Implement: int numberOfHours(char[][] mat) => returns 3 for example above


  • 0
    D

    If anyone have solution for this?


  • 0
    C

    You can go with a BFS approach in O(n*m):

    push all the 'W' cells to a queue and set their cost to 0
    start processing cells from the queue
      for the current cell (x,y)
        add all the 'E' neighbors (x', y') to the queue
        setting the cost(x', y') = cost(x, y) + 1
        also change (x', y') from 'E' to 'W'
    return the cost of the last cell from the queue (which is also the greatest).
    

    every cell gets pushed to the queue at most one time, so the overall time complexity ends up being O(n*m)


  • 0
    E

    @raghavachar

    #define ROW 3
    #define COL 3
    
    int main(void) {
        puts("Hello World!");
        char x[3][3] = {{'E', 'E', 'E'}, {'E', '#', 'W'}, {'E', 'W', 'E'}};    
        int loop = 0;
        char hit_char;
        int hit = 0;
            for (int row=0; row<ROW; row++) {
                for (int col=0; col<COL; col++) {
                    printf ("%c ", x[row][col]);
                }
            }    
        while (1) {
            hit_char = 'W'+loop;
            hit = 0;
            printf("hit char = %c\n", hit_char);
            
            for (int row=0; row<ROW; row++) {
                for (int col=0; col<COL; col++) {
    
                    if (x[row][col] == hit_char) {
                        
                        if(row) {  // has_top
                            if (x[row-1][col] == 'E') {
                                hit = 1;
                                x[row-1][col] = hit_char + hit;
                            }
                        }
                
                        if(col) { // has_left
                            if (x[row][col-1] == 'E') {
                                hit = 1;
                                x[row][col-1] = hit_char + 1;
                            }
                        }
                
                        if(row+1 < ROW) { // has_bottom
                            if (x[row+1][col] == 'E') {
                                hit = 1;
                                x[row+1][col] = hit_char + 1;
                            }                                        
                        }
                   
                        if(col+1 < COL) { // has_right
                            if (x[row][col+1] == 'E') {
                                hit = 1;
                                x[row][col+1] = hit_char + 1; 
                            }                    
                        }
                    }                   
                }
            }
            
            if (hit) loop++;
            else break;
            for (int row=0; row<ROW; row++) {
                for (int col=0; col<COL; col++) {
                    printf ("%c ", x[row][col]);
                }
            }
        }
        printf ("loop = %d\n", loop);
        return 0;
    }

  • 0
    I

    @raghavachar said in Farm land with cells Empty, Water and Barrier:

    E E E
    E # W
    E W E

         public int numberOfHours(char[][] mat) {
    	int result = 0;
    	boolean isAvailable = true;
    	while(isAvailable) {
    	  for(int i=0; i<mat.length; i++) {
    	    for(int j=0; j<mat[i].length; j++) {
    	        if(mat[i][j] == 'W') {
    			//Look Bottom
    			if((i-1) != -1 && mat[i-1][j] == 'E') {
    				mat[i-1][j] = 'W'
    			}//Look Left
    			if((j-1) != -1 && mat[i][j-1] == 'E') {
    				mat[i][j-1] = 'W';
    			}//Look Top
    			if((i+1) < mat.length && mat[i+1][j] == 'E') {
    				mat[i+1][j] = 'W';
    			}//Look Right
    			if((j+1) < mat[i].length && mat[i][j+1] == 'E') {
    				mat[i][j+1] = 'W';
    			}		
    		}
    	}
    	for(int x=0; x<mat.length; x++) {
    		for(int y=0; y<mat[x].length; y++) {
    			if(mat[x][y] == 'E') {
    				isAvailable = true;
    				break;
    			} else {
    				isAvailable = false;
    			}
    		}
    		if(isAvailable) break;
    	   }
          }
          result++;
       }
    	
    	return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.