LeetCode130 被围绕的区域（后续）

Question

老师，按照您的建议我重新修改了一下代码，第25个用例没通过，您能帮忙看下是逻辑上的问题还是其他细节问题嘛

public class LeetCode130 {
    boolean[][] flag;
    int[][] go = {{-1,0},{0,1},{1,0},{0,-1}};
    int m,n;
    //设置一个判断遍历元素中是否有边界元素的标志
    boolean isBoundaryFlag;
    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'){
                    dfs(board,i,j,false);
                }
            }
        }
    }
    private void dfs(char[][] board,int startX,int startY,boolean isBoundaryFlag){
        //是否为边界元素，如果是将标志位改变回溯
        if (isBoundary(startX,startY)){
            isBoundaryFlag = true;
            return;
        }
        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)&&!flag[newX][newY]&&board[startX][startY]=='O'){
                dfs(board,newX,newY,isBoundaryFlag);
            }
            if (isBoundaryFlag){
                board[startX][startY]='O';
                break;
            }
        }
        return;
    }
    //判断是否为边界元素
    private boolean isBoundary(int x,int y){
        if (x==m-1||x==0||y==n-1||y==0){
            return true;
        }else {
            return false;
        }
    }
    //判断坐标是否在矩阵内
    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-30 04:17:47

首先，先不考虑具体的逻辑，你的代码中的 isBoundaryFlag 这个变量的设置是有问题的。

首先，你设置了两个 isBoundaryFlag，一个是类变量，一个是 dfs 中的参数。因为 dfs 中的参数和类变量的名字一样，都是 isBoundaryFlag，所以在这个函数内，这个参数覆盖了类变量 isBoundaryFlag，那么首先，类变量 isBoundaryFlag 是没有用的。

其次，如果只看 dfs 中的参数 isBoundaryFlag，你对这个参数的操作也是没有意义的。你改变了这个参数，然后直接 return 了。这个改变没有影响任何逻辑，因为 boolean 是基本数据类型，所以这个改变也不会传回上一层。

==========

如果考虑具体逻辑，先不说逻辑框架是否正确，你现在的代码是有小 bug 的。我不告诉你这个 Bug 是什么。我试了一下，你现在的代码，在 leetcode 中出错的用例是：

1 2 3

OOO OOO OOO

这是一个足够小的用例，只有 3 * 3 的 board，且答案显而易见，没有任何点应该改变。请你仔细调试你的代码，在调试过程中一步一步去看，你的代码在实际执行过程中，每一步把程序中的变量变成了什么，但是你希望的是变成什么，或者你以为的是变成什么。和你以为的是不是一样？如果不一样，自己哪里想错了。

=========

当你能把你的程序先调成能正确表达你想表达的逻辑的程度，你可能会发现你现在想的这个算法是有问题的。但是等你发现了这个问题，你想不通了，可以再来提问。

我希望你的问题是：

1）在某个用例下，你觉得你的逻辑应该得到怎样的结果，但实际却得到了怎样的结果，你想不明白了；

2）或者你明白原因出在哪里了，但是不知道怎么解决了；

3）或者出错的测试用例非常大，你很难去排查了，所以不知道该怎么做了。

如果你不去这么调试程序，你永远不能进步。对程序更深刻的理解，就在这个调试的过程，自己找到自己思维漏洞的过程中。

继续加油！：）