# Farm land with cells Empty, Water and Barrier

• 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

• If anyone have solution for this?

• 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)

• @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;
}``````

• 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;
}``````

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