LeetCode130 被围绕的区域

Question

老师，您能帮忙看下问题出在哪嘛，总感觉我的递归终止条件和for循环内的判断逻辑理不清楚，您能给个思路或者建议嘛？

public class LeetCode130 {
    boolean[][] flag;
    int[][] go = {{-1,0},{0,1},{1,0},{0,-1}};
    int m,n;
    public void solve(char[][] board) {
        m = board.length;
        if (m<1){
            return;
        }
        n = board[0].length;
        flag = new boolean[m][n];
        for (int i = 1; i < m-1; i++) {
            for (int j = 1;j<n-1;j++){
                if (!flag[i][j]&&board[i][j]=='O'){
                    bfs(board,i,j,true);
                }
            }
        }
    }
    private boolean bfs(char[][] board,int startX,int startY,boolean flag1){
        //如果不是O返回false
        if (board[startX][startX]!='O'){
            return false;
        }
        //如果是O但是处于边界
        if (board[startX][startY]=='O'&&!judgeBoard(startX,startY)){
            flag1=false;
            return false;
        }
        flag[startX][startY]=true;
        board[startX][startY]='X';
        for (int i = 0;i<4;i++){
            int newX = startX+go[i][0];
            int newY = startY+go[i][1];
            if (inArea(newX,newY)&&judgeBoard(newX,newY)){
                boolean a = bfs(board,newX,newY,flag1);
                if (!flag1){
                    board[startX][startY]='O';
                    return false;
                }
            }
        }
        return true;
    }
    //判断是否为边界元素
    private boolean judgeBoard(int x,int y){
        if (x==m-1||x==0){
            return false;
        }else return y != n - 1 && y != 0;
    }
    //判断是否在边界内
    private boolean inArea(int x,int y){
        if ((x>=0&&x<m)&&(y>=0&&y<n)){
            return true;
        }else {
            return false;
        }
    }
}

Answer 1

liuyubobobo 2022-03-29 16:34:25

我没有看完你的代码。因为看到一半就懵了。因为语义不清晰。

请回答以下问题：

1）bfs 函数（实际上你使用的是 dfs） 的返回值是什么意思？

2）bfs 函数参数中的 flag1 表示什么意思？

3）什么叫 judgeBoard？这个名字看似把这个函数要做什么写出来了，但其实没有用。请问到底是传进去的点在边界上返回 true？还是不在边界上返回 true？如果这个函数是在判断一个点是在边界上，是不是叫 inBorder 更清晰？（或者 notInBorder）

4）猛地看你的逻辑，flag1 初始传进去 true，似乎永远是 true，不会改变，唯一变化 flag1 的地方在一个 if 中，之后马上 return 了，所以这个改变也没有影响任何逻辑。但 anyway，关键还是，你的 flag1 到底是什么意思。（另外一点就是整个函数的返回值似乎在逻辑中也没有用。）

你必须用自然语言能够讲清楚你的函数的每一个变量的语义是什么，我才能看到你的逻辑是不是围绕这些语义展开的，才能验证你的逻辑是否正确，你自己也能检查这一点。这是我给看了你的这版代码，给你的唯一的建议。这个建议本身，也是写程序（不仅仅是算法）需要遵循的首要原则。

继续加油！：）

• 提问者 不考过程序员不改名字 #1

  老师，按照您说的我梳理了下逻辑重新写了一遍，第25个用例没通过，您能帮忙看下整体逻辑有什么问题嘛
  ，回复里贴不了代码我重新再发一个