LeetCode130 被围绕的区域
来源:8-7 floodfill算法,一类经典问题 Number of Islands-
不考过程序员不改名字
2022-03-29
老师,您能帮忙看下问题出在哪嘛,总感觉我的递归终止条件和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;
}
}
}
写回答
1回答
-
liuyubobobo
2022-03-29
我没有看完你的代码。因为看到一半就懵了。因为语义不清晰。
请回答以下问题:
1)bfs 函数(实际上你使用的是 dfs) 的返回值是什么意思?
2)bfs 函数参数中的 flag1 表示什么意思?
3)什么叫 judgeBoard?这个名字看似把这个函数要做什么写出来了,但其实没有用。请问到底是传进去的点在边界上返回 true?还是不在边界上返回 true?如果这个函数是在判断一个点是在边界上,是不是叫 inBorder 更清晰?(或者 notInBorder)
4)猛地看你的逻辑,flag1 初始传进去 true,似乎永远是 true,不会改变,唯一变化 flag1 的地方在一个 if 中,之后马上 return 了,所以这个改变也没有影响任何逻辑。但 anyway,关键还是,你的 flag1 到底是什么意思。(另外一点就是整个函数的返回值似乎在逻辑中也没有用。)
你必须用自然语言能够讲清楚你的函数的每一个变量的语义是什么,我才能看到你的逻辑是不是围绕这些语义展开的,才能验证你的逻辑是否正确,你自己也能检查这一点。这是我给看了你的这版代码,给你的唯一的建议。这个建议本身,也是写程序(不仅仅是算法)需要遵循的首要原则。
继续加油!:)
012022-03-29
相似问题
LeetCode130求教
回答 1
BoBo老师,一道饿了么的机试题
回答 1