r**h
发帖数: 1288 | 1 具体代码如下，思路就是从每个边界节点为起点做dfs，最后将未被访问到的'O'设置成
'X'
查看了一下，每个节点只被访问过一遍，不知道为什么结果TLE了。请大家帮忙看一下
，谢谢~
public class Solution {
int[][] direction = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
public void solve(char[][] board) {
// Start typing your Java solution below
// DO NOT write main() function
if(board.length == 0) return;
int m=board.length, n=board[0].length;
if(m<=2 || n<=2) return;
int[][] visited = new int[m][n];
for(int i=0; i
if(visited[0][i] == 0 && board[0][i] == 'O')
dfs(board, visited, 0, i);
if(visited[m-1][i] == 0 && board[m-1][i] == 'O')
dfs(board, visited, m-1, i);
}
for(int i=1; i
if(visited[i][0] == 0 && board[i][0] == 'O')
dfs(board, visited, i, 0);
if(visited[i][n-1] == 0 && board[i][n-1] == 'O')
dfs(board, visited, i, n-1);
}
for(int i=1; i
for(int j=1; j
if(visited[i][j]==0 && board[i][j]=='O')
board[i][j] = 'X';
}
}
return;
}
public void dfs(char[][] board, int[][] visited, int i, int j){
visited[i][j] = 1;
int ni, nj;
for(int n=0; n<4; n++){
ni = i+direction[n][0];
nj = j+direction[n][1];
if(ni>=0 && ni=0 && nj
if(visited[ni][nj] == 0 && board[ni][nj] == 'O')
dfs(board, visited, ni, nj);
}
}
}
} | r*******e
发帖数: 7583 | 2 DFS可能的问题是call stack太深了
换成BFS吧
【在 r**h 的大作中提到】
: 具体代码如下，思路就是从每个边界节点为起点做dfs，最后将未被访问到的'O'设置成
: 'X'
: 查看了一下，每个节点只被访问过一遍，不知道为什么结果TLE了。请大家帮忙看一下
: ，谢谢~
: public class Solution {
: int[][] direction = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
:
: public void solve(char[][] board) {
: // Start typing your Java solution below
: // DO NOT write main() function
|
|
