leetcode130问题，波波老师麻烦帮我分析一下，不知道哪里出了问题

Question

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

boolean[][] visited;     int m;     int n;     int[][] move = {{0,1},{-1,0},{0,-1},{1,0}};     public void solve(char[][] board) {           m = board.length;           if(m==0)               return;           n = board[0].length;           visited = new boolean[m][n];                       for(int i= 0 ;i<m;i++){               for(int j=0;j<n;j++){                   if(board[i][j] == 'O' && !visited[i][j]){                       mark(i,j,board);                     }               }           }         return;         }       private boolean mark(int i, int j, char[][] board) {         visited[i][j] = true;                   boolean lable = false;                   if(i==m-1 || j==n-1 || i==0 || j==0)             lable =  true;                   for(int k=0; k<4; k++){             int newx = i + move[k][0];             int newy = j + move[k][1];             if(inarea(newx,newy) && !visited[newx][newy] && board[newx][newy]=='O'){                 lable  = mark(newx,newy,board) || lable ;             }             if(!lable)                 board[i][j] = 'X';         }                   return lable;               }       private boolean inarea(int i, int j) {         return i>=0 && j>=0 && i<m && j<n;     }

Answer 1

liuyubobobo 2018-08-14 18:38:36

130使用DFS无法ac，因为极端数据会导致栈溢出，可以参考这里的注释：）

https://github.com/liuyubobobo/Play-Leetcode/blob/master/0130-Surrounded-Regions/cpp-0130/main.cpp

改成BFS就ok了：）加油！

• 提问者 慕工程2559728 #1

  非常感谢！

• 慕神9346227 #2

  老师，这段代码速度上只击败了37%，有优化速度的方法吗

• liuyubobobo 回复 慕神9346227 #3

  leetcode 上的这个百分比不准，很多时候一个问题刚开始测试数据比较小，后来测试数据越来越大，导致不可能超越前面的程序。我个人不建议在非复杂度级别的优化上花时间，但一定感兴趣，Accepted Solutions Runtime Distribution 里面的百分比分布图是可以点击的，进而可以查看研究实验别人的代码。加油！：）