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

Question

 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 里面的百分比分布图是可以点击的，进而可以查看研究实验别人的代码。加油！：）