package Week04;

import javafx.util.Pair;

import java.util.*;

public class Amazon_Interview {

/*

* 历遍矩阵，找到0时，广度优先，一层层扩展（水波纹），找到最近的‘1’

* 最后输出最大的

* */

int nr,nc;

int[][] dir = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};

public int daysOfUpdate(int rows, int columns, char[][] grid) {

int ans = -1;

if (rows <=0 || columns<=0) {

return ans;

}

nr = rows;

nc = columns;

for (int i=0;i<rows;i++){

for(int j = 0;j<columns;j++){

if (grid[i][j] == '0'){

int res = bfs(grid,i,j);

ans = Math.max(ans,res);

}

}

}

return ans;

}

private int bfs(char[][] grid,int row, int col){

int level = 0;

int x,y;

Queue<Pair<Integer,Integer>> queue = new ArrayDeque<>();

Set<Pair<Integer,Integer>> visited = new HashSet<>();

for (int[] d : dir) {

addQueue(row+d[0],col+d[1],queue);

}

while(!queue.isEmpty()){

level++;

int size = queue.size();

for (int i =0;i<size;i++){

Pair<Integer,Integer> key = queue.poll();

if (!visited.contains(key)){

x = key.getKey();

y = key.getValue();

if (grid[x][y] == '1') {

return level;

}

visited.add(key);

for (int[] d : dir) {

addQueue(x+d[0],y+d[1],queue);

}

}

}

}

return 0;

}

private void addQueue(int r, int c, Queue<Pair<Integer,Integer>> queue) {

if (0<= r && r<nr && 0<=c && c<nc){

queue.add(new Pair<>(r,c));

}

}

}

class test{

public static void main(String[] args) {

Amazon_Interview solution = new Amazon_Interview();

int row =4,col =5;

char[][] grid = new char[4][5];

// grid[0]= new char[]{'0', '1', '1', '0', '1'};

// grid[1]= new char[]{'0', '1', '0', '1', '0'};

// grid[2]= new char[]{'0', '0', '0', '0', '1'};

// grid[3]= new char[]{'0', '1', '0', '0', '0'};

// int row =2,col =4;

// char[][] grid = new char[2][4];

// grid[0]= new char[]{'0', '0', '0', '0'};

// grid[1]= new char[]{'0', '0', '0', '1'};

grid[0]= new char[]{'0', '0', '0', '0', '0'};

grid[1]= new char[]{'0', '0', '0', '0', '0'};

grid[2]= new char[]{'0', '0', '0', '0', '0'};

grid[3]= new char[]{'0', '0', '0', '0', '1'};

int res = solution.daysOfUpdate(row,col,grid);

System.out.println("res="+res);

}

}