孤岛迭代矩阵个数，标记访问节点个数

Question

对问题的描述:https://leetcode.com/problems/number-of-islands/

基本上你有一个由1和0组成的矩阵，你需要数一数有多少组1。

尽管有很多print语句，我还是不明白为什么这段代码不工作。我在矩阵中迭代，每当我看到一个1，我就进行深度优先搜索，并将1加上周围所有的15变为0 -标记这些节点被访问过。

我错过了什么?

class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[i].length; j++) {
//System.out.println(grid[i][j]);
if(grid[i][j] == '1') {
// System.out.println("i = " + i);
// System.out.println("j = " + j);
countIslands(grid, i, j);
count++;
}
}
}
return count;
}

public static void countIslands(char[][] grid, int sr, int sc) {
grid[sr][sc] = '0';

final int[][] SHIFTS = {
{0,1}, //move right
{1,0}, //move down
{0,-1}, //move left
{-1,0} //move up
};

for(int[] shift : SHIFTS) {
sr = sr + shift[0];
sc = sc + shift[1];

if(moveValid(grid, sr, sc)) {
countIslands(grid, sr, sc);
}
}
}

public static boolean moveValid(char[][] grid, int sr, int sc) {
if(sr >= 0 && sr < grid.length && sc >= 0 && sc < grid[sr].length && grid[sr][sc] == '1') {
return true;
}
return false;
}
}

Answer 1

非常好的问题。依我看，错误在以下几行:

for(int[] shift : SHIFTS) {
sr = sr + shift[0];
sc = sc + shift[1];

if(moveValid(grid, sr, sc)) {
countIslands(grid, sr, sc);
}
}

在这里你继续增加sr和sc，而你顺时针旋转。所以你的搜索会比你第一眼想象的要深入。

Answer 2

这部分代码有一个错误-

for(int[] shift : SHIFTS) {
sr = sr + shift[0];
sc = sc + shift[1];

if(moveValid(grid, sr, sc)) {
countIslands(grid, sr, sc);
}
}

您正在修改sr, sc并重新使用它来获取其他相邻字段。因此假设最初sr=1 sc =1。所有相邻的单元格为(1,0)，(2,1)，(0,1)和(1,2)。

但是在上面的代码中，相邻的单元格是这样构造的，首先是sr=1 sc=1然后是sr=1 sc=2，所以接下来你使用(1,2)来获得相邻的单元格，其中还包括(1,3)，它不是(1,1)的相邻单元格。

正确的做法是-

for(int[] shift : SHIFTS) {
int nsr = sr + shift[0];
int nsc = sc + shift[1];

if(moveValid(grid, nsr, nsc)) {
countIslands(grid, nsr, nsc);
}
}