z****e
发帖数: 54598 | 1 java的，二爷博客上的java的bfs有个bug
不过在leetcode上测不出来就是了，当m!=n的时候，二爷代码就出错了
这题真心坑爹，尤其用java做
递归的调用很容易就超时了
所以我在二爷代码的基础之上做了点优化
大概能优化50ms左右，对于小oj来说
大oj还是需要连点两次，激活jvm的jit才能过
public class Solution {
char[][] board;
int m,n;
Stack queue = new Stack();
private void fill(int i, int j){
if(i<0||j<0||i>=m||j>=n||board[i][j]!='O') return;
board[i][j] = 'D';
queue.push(i*n+j);
}
private void bfs(int i, int j){
fill(i,j);
while(!queue.isEmpty()){
int cur = queue.pop();
i = cur/n;
j = cur%n;
fill(i-1,j);
fill(i+1,j);
fill(i,j-1);
fill(i,j+1);
}
}
public void solve(char[][] board){
if(board.length == 0) return;
this.board = board;
m = board.length;
n = board[0].length;
for(int i=0;i
bfs(0, i);
bfs(m-1,i);
}
for(int i=1;i
bfs(i,0);
bfs(i,n-1);
}
for(int i=0;i
for(int j=0;j
if(board[i][j]=='O') board[i][j] = 'X';
else if(board[i][j]=='D') board[i][j] = 'O';
}
}
}
} | c********p
发帖数: 1969 | | c********e
发帖数: 186 | 3 先mark再说
【在 z****e 的大作中提到】
: java的，二爷博客上的java的bfs有个bug
: 不过在leetcode上测不出来就是了，当m!=n的时候，二爷代码就出错了
: 这题真心坑爹，尤其用java做
: 递归的调用很容易就超时了
: 所以我在二爷代码的基础之上做了点优化
: 大概能优化50ms左右，对于小oj来说
: 大oj还是需要连点两次，激活jvm的jit才能过
: public class Solution {
:
: char[][] board;
|
|
