LeetCode130 被围绕的区域（后续）
来源：8-7 floodfill算法，一类经典问题 Number of Islands-
不考过程序员不改名字
2022-03-29
老师，按照您的建议我重新修改了一下代码，第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;
}
}
}
1回答
-
liuyubobobo
2022-03-30
首先，先不考虑具体的逻辑，你的代码中的 isBoundaryFlag 这个变量的设置是有问题的。
首先，你设置了两个 isBoundaryFlag，一个是类变量，一个是 dfs 中的参数。因为 dfs 中的参数和类变量的名字一样，都是 isBoundaryFlag，所以在这个函数内，这个参数覆盖了类变量 isBoundaryFlag，那么首先，类变量 isBoundaryFlag 是没有用的。
其次，如果只看 dfs 中的参数 isBoundaryFlag，你对这个参数的操作也是没有意义的。你改变了这个参数，然后直接 return 了。这个改变没有影响任何逻辑，因为 boolean 是基本数据类型，所以这个改变也不会传回上一层。
==========
如果考虑具体逻辑，先不说逻辑框架是否正确，你现在的代码是有小 bug 的。我不告诉你这个 Bug 是什么。我试了一下，你现在的代码，在 leetcode 中出错的用例是：
OOO OOO OOO
这是一个足够小的用例，只有 3 * 3 的 board，且答案显而易见，没有任何点应该改变。请你仔细调试你的代码，在调试过程中一步一步去看，你的代码在实际执行过程中，每一步把程序中的变量变成了什么，但是你希望的是变成什么，或者你以为的是变成什么。和你以为的是不是一样？如果不一样，自己哪里想错了。
=========
当你能把你的程序先调成能正确表达你想表达的逻辑的程度，你可能会发现你现在想的这个算法是有问题的。但是等你发现了这个问题，你想不通了，可以再来提问。
我希望你的问题是：
1）在某个用例下，你觉得你的逻辑应该得到怎样的结果，但实际却得到了怎样的结果，你想不明白了；
2）或者你明白原因出在哪里了，但是不知道怎么解决了；
3）或者出错的测试用例非常大，你很难去排查了，所以不知道该怎么做了。
如果你不去这么调试程序，你永远不能进步。对程序更深刻的理解，就在这个调试的过程，自己找到自己思维漏洞的过程中。
继续加油！：）
10
相似问题
回答 1
回答 1