200题答案有错，求debug

求debug。感谢  (可以运行但是答案是错的)

顺便求一粒米看面镜～～～

1. class Solution {
   
2.    
   
3.     int count = 0;
   
4.    
   
5.     int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
   
6.    
   
7.     public int numIslands(char[][] grid) {
   
8.         
   
9.         int r = grid.length;
   
10.         int c = grid[0].length;
    
11.          
    
12.         for(int m = 0; m < r; m++)
    
13.             for(int n = 0; n < c; n++)
    
14.                     if(  grid[m][n] == '1' ) {
    
15.                         
    
16.                         System.out.println("we found one island!!");
    
17.                         
    
18.                         count++;
    
19.                         
    
20.                         bfs(grid, m, n, r, c);
    
21.                     }   
    
22.         
    
23.         return count;
    
24.     }
    
25.    
    
26.     public void bfs(char[][] grid, int i, int j, int r, int c) {
    
27.         
    
28.         Queue<int[]> q = new LinkedList<int[]>();
    
29.         
    
30.         q.add(new int[]{i,j});
    
31.       
    
32.         while(!q.isEmpty()){
    
33.             
    
34.                 int[] curr = q.poll();
    
35. 
    
36.                 grid[ curr[0] ][ curr[1] ] = '0';
    
37. 
    
38.                 for(int[] dir : dirs) {
    
39. 
    
40.                     int ii = i + dir[0];
    
41.                     int jj = j + dir[1];
    
42. 
    
43.                     if( ii>=0 && ii < r && jj>=0 && jj < c && grid[ii][jj] == '1' ){
    
44.                         
    
45.                         System.out.println("we add into queue = " + ii + "   " + jj  +  "  <--    " + i + "    " + j   );
    
46.                         q.add(new int[]{ii,jj});
    
47.                     }
    
48.                 }
    
49.         }        
    
50.     }   
    
51. }

复制代码

这个解逻辑上的错误在40、41两行。这个错误我也会犯lol。
我建议使用单独的变量明示。比如：
1. 不要图省事直接使用cur[0]/cur[1](实际上也没有特别省事)。而使用: <code>int row = cur[0]; int col = cur[1];</code>明示。新的坐标使用新的变量明示：<code>int r = row + dirs[0]; int c = col + dirs[1]</code>。这样比较不容易犯错。
2. 个人觉得:使用的变量的名称，有些不习惯。比如避免使用单字母的变量(q -> queue)，使用row/col代替i/j, r(nr)/c(nc)代替ii/jj等。这可能是一个个人习惯的问题。

三个问题：1. 应该在入队之前标记visited，不然会重复入队。2. 40行改成int ii = curr[0] + dir[0]; 41行同理。 3. 缺少边界条件判断。
两个建议： 1. 建议楼主弄懂每个算法具体原理再做题。 2. 不要生搬硬套模板，要弄懂每一行代码都是做什么的，写完之后自己按照自己写的代码手动在纸上跑一遍。

crest300 发表于 2020-9-22 05:29
三个问题：1. 应该在入队之前标记visited，不然会重复入队。2. 40行改成int ii = curr[0] + dir[0]; 41行同 ...

万分感谢！！！！！！！！！！

crest300 发表于 2020-9-22 05:29
三个问题：1. 应该在入队之前标记visited，不然会重复入队。2. 40行改成int ii = curr[0] + dir[0]; 41行同 ...

感谢回答，我有些小疑问。还请多多指教：
这题目，只会把是1的点(岛)放入队列，出队后再标记为0。逻辑上应该不会出现重复加入队列的情况。
不过我同意：常规BFS应该在进队列的时候进行标记。相比较而言，Djikstra's Algorithm是出队列的时候进行标记。

我也不太董这里说的"缺少边界判断"是什么意思。43行不算么？

debug结束了，通过了

1. class Solution {
   
2.    
   
3.     int count = 0;
   
4.    
   
5.     int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
   
6.    
   
7.     public int numIslands(char[][] grid) {
   
8.         
   
9.         if(grid.length == 0) return 0;
   
10.         
    
11.         int r = grid.length;
    
12.         int c = grid[0].length;
    
13.          
    
14.         for(int m = 0; m < r; m++)
    
15.             for(int n = 0; n < c; n++)
    
16.                     if(  grid[m][n] == '1' ) {
    
17.                        
    
18.                         count++;
    
19.                         
    
20.                         bfs(grid, m, n, r, c);
    
21.                     }   
    
22.         
    
23.         return count;
    
24.     }
    
25.    
    
26.     public void bfs(char[][] grid, int i, int j, int r, int c) {
    
27.         
    
28.         Queue<int[]> q = new LinkedList<int[]>();
    
29.         
    
30.         q.add(new int[]{i,j});
    
31.         
    
32.         grid[ i ][ j ] = '0';
    
33.       
    
34.         while(!q.isEmpty()){
    
35.             
    
36.                 int[] curr = q.poll();
    
37.             
    
38.                 grid[ curr[0] ][ curr[1] ] = '0';
    
39. 
    
40.                 for(int[] dir : dirs) {
    
41. 
    
42.                     int ii = curr[0] + dir[0];
    
43.                     int jj = curr[1] + dir[1];
    
44. 
    
45.                     if( ii>=0 && ii < r && jj>=0 && jj < c && grid[ii][jj] == '1' ){
    
46.                         
    
47.                         q.add(new int[]{ii,jj});
    
48.                         grid[ii][jj] = '0';
    
49.                     }
    
50.                 }
    
51.         }        
    
52.     }   
    
53. }
    

复制代码

                    int ii = i + dir[0];
                    int jj = j + dir[1];

这里错了， i, j 不是当前queue弹出来的那个坐标了

crest300 发表于 2020-9-22 05:29
三个问题：1. 应该在入队之前标记visited，不然会重复入队。2. 40行改成int ii = curr[0] + dir[0]; 41行同 ...

确定有这2个问题吗？

把值从1改成0（就是相当于visited flag），就是防止重复入队
边界也有判断，在入队的时候

ygmm 发表于 2020-9-23 11:27
确定有这2个问题吗？

把值从1改成0（就是相当于visited flag），就是防止重复入队

您可以尝试提交一下楼主最开始没改过的代码哦，谢谢亲~~