Leetcode 的 Surrounded Regions 好难过大OJ (in JAVA)# JobHunting - 待字闺中
B*7
1 楼
自己写了一个code，和大多数网上的code一样，基本思路就是bfs。但要过大oj还真不
容易。我refactor了半天也只能有大概一半的概率过。过的时候时间都是800 ms 以下
（～750 ms），只有一次到过800 ms. 所以强烈怀疑这道题的时间上限是800 ms. LOL
我附了code，用java写的。大牛们帮忙看看该怎么改进？先谢谢啦。
public class Solution {
public void solve(char[][] board) {
// Start typing your Java solution below
// DO NOT write main() function
int m = board.length;
if( m == 0 ) return;
int n = board[0].length;
// special cases
if( m < 3 || n < 3 ) return;
// process edges
//-- top and bottom
for(int j = 0; j < n; j++ ) {
if( board[0][j] == 'O' ) Helper.bfs( board, 0, j );
if( board[m-1][j] == 'O' ) Helper.bfs( board, m - 1, j );
}
//-- left and right
for(int i = 1; i < m - 1; i++ ) {
if( board[i][0] == 'O' ) Helper.bfs( board, i, 0 );
if( board[i][n-1] == 'O' ) Helper.bfs( board, i, n - 1 );
}
// change back not surrounded blocks
for( int i = 0; i < m ; i++ ) {
for( int j = 0; j < n; j++ ) {
if( board[i][j] == 'Y' ) board[i][j] = 'O';
else if( board[i][j] == 'O' ) board[i][j] = 'X';
}
}
}
static class Helper {
// for BFS
private static ArrayDeque iqueue = new ArrayDeque(
);
private static ArrayDeque jqueue = new ArrayDeque(
);
public static void bfs( char[][] board, int i, int j ) {
int m = board.length;
int n = board[0].length;
board[i][j] = 'Y';
iqueue.add( i );
jqueue.add( j );
while( !iqueue.isEmpty() ) {
i = iqueue.poll();
j = jqueue.poll();
// neighbors: [i+/-1, j], [i, j+/-1]
// [i+1,j]
if( i < m - 1 && board[i+1][j] == 'O' ) {
board[i+1][j] = 'Y';
iqueue.add( i+1 );
jqueue.add( j );
}
// [i-1, j]
if( i > 0 && board[i-1][j] == 'O' ) {
board[i-1][j] = 'Y';
iqueue.add( i-1 );
jqueue.add( j );
}
// [i, j+1]
if( j < n - 1 && board[i][j+1] == 'O' ) {
board[i][j+1] = 'Y';
iqueue.add( i );
jqueue.add( j+1 );
}
// [i, j-1]
if( j > 0 && board[i][j-1] == 'O' ) {
board[i][j-1] = 'Y';
iqueue.add( i );
jqueue.add( j-1 );
}
}
}
}
}
容易。我refactor了半天也只能有大概一半的概率过。过的时候时间都是800 ms 以下
（～750 ms），只有一次到过800 ms. 所以强烈怀疑这道题的时间上限是800 ms. LOL
我附了code，用java写的。大牛们帮忙看看该怎么改进？先谢谢啦。
public class Solution {
public void solve(char[][] board) {
// Start typing your Java solution below
// DO NOT write main() function
int m = board.length;
if( m == 0 ) return;
int n = board[0].length;
// special cases
if( m < 3 || n < 3 ) return;
// process edges
//-- top and bottom
for(int j = 0; j < n; j++ ) {
if( board[0][j] == 'O' ) Helper.bfs( board, 0, j );
if( board[m-1][j] == 'O' ) Helper.bfs( board, m - 1, j );
}
//-- left and right
for(int i = 1; i < m - 1; i++ ) {
if( board[i][0] == 'O' ) Helper.bfs( board, i, 0 );
if( board[i][n-1] == 'O' ) Helper.bfs( board, i, n - 1 );
}
// change back not surrounded blocks
for( int i = 0; i < m ; i++ ) {
for( int j = 0; j < n; j++ ) {
if( board[i][j] == 'Y' ) board[i][j] = 'O';
else if( board[i][j] == 'O' ) board[i][j] = 'X';
}
}
}
static class Helper {
// for BFS
private static ArrayDeque
);
private static ArrayDeque
);
public static void bfs( char[][] board, int i, int j ) {
int m = board.length;
int n = board[0].length;
board[i][j] = 'Y';
iqueue.add( i );
jqueue.add( j );
while( !iqueue.isEmpty() ) {
i = iqueue.poll();
j = jqueue.poll();
// neighbors: [i+/-1, j], [i, j+/-1]
// [i+1,j]
if( i < m - 1 && board[i+1][j] == 'O' ) {
board[i+1][j] = 'Y';
iqueue.add( i+1 );
jqueue.add( j );
}
// [i-1, j]
if( i > 0 && board[i-1][j] == 'O' ) {
board[i-1][j] = 'Y';
iqueue.add( i-1 );
jqueue.add( j );
}
// [i, j+1]
if( j < n - 1 && board[i][j+1] == 'O' ) {
board[i][j+1] = 'Y';
iqueue.add( i );
jqueue.add( j+1 );
}
// [i, j-1]
if( j > 0 && board[i][j-1] == 'O' ) {
board[i][j-1] = 'Y';
iqueue.add( i );
jqueue.add( j-1 );
}
}
}
}
}
