leetcode# JobHunting - 待字闺中
z*e
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(m-1,i);
}
for(int i=1;i
bfs(i,n-1);
}
for(int i=0;i
else if(board[i][j]=='D') board[i][j] = 'O';
}
}
}
}
不过在leetcode上测不出来就是了，当m!=n的时候，二爷代码就出错了
这题真心坑爹，尤其用java做
递归的调用很容易就超时了
所以我在二爷代码的基础之上做了点优化
大概能优化50ms左右，对于小oj来说
大oj还是需要连点两次，激活jvm的jit才能过
public class Solution {
char[][] board;
int m,n;
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(m-1,i);
}
for(int i=1;i
bfs(i,n-1);
}
for(int i=0;i
else if(board[i][j]=='D') board[i][j] = 'O';
}
}
}
}
