找能去的所有0区域
给一个二维matrix,-1代表墙,0代表路。问给定一个起点坐标为0,是否能到达所有的0。
public class AllReachableZero {
public boolean findAllReachableZero(int[][] matrix, int x, int y)
{
boolean[][] visited = new boolean[matrix.length][matrix[0].length];
dfs(matrix, x, y, visited);
for(int i = 0; i< matrix.length; i++)
{
for(int j = 0; j< matrix[0].length; j++)
{
if(!visited[i][j] && matrix[i][j] == 0)
{
return false;
}
}
}
return true;
}
public void dfs(int[][] matrix, int i, int j, boolean[][] visited)
{
if(!isBound(matrix, i, j) || visited[i][j] || matrix[i][j] == -1 || matrix[i][j] == 1)
{
return;
}
visited[i][j] = true;
matrix[i][j] = 1;
dfs(matrix, i-1, j, visited);
dfs(matrix, i+1, j, visited);
dfs(matrix, i, j-1, visited);
dfs(matrix, i, j+1, visited);
}
public boolean isBound(int[][] matrix, int i, int j)
{
return i>=0 && i<matrix.length && j>=0 && j<matrix[0].length;
}
}
Last updated