d********m
发帖数: 101 | 1 思路是从4个边界分别检测，如果是O就替换为T。最后在整体遍历一次，把O的改为X，T
改为O。
过不去的那个test case超级长，自己测不了。麻烦各位大侠给看看代码。
谢谢先～
class Solution {
public:
void turn (int row, int col, vector> &board) {
if (row < 0 || row >= board.size() || col < 0 || col >= board[0].
size() || board[row][col] != 'O' ) {
return;
}
board[row][col] = 'T';
turn(row + 1, col, board);
turn(row - 1, col, board);
turn(row, col + 1, board);
turn(row, col - 1, board);
}
void solve(vector> &board) {
int m = board.size();
if (m == 0) return;
int n = board[0].size();
for (int row = 0; row < m; row++) {
turn(row,0,board);
turn(row,n - 1,board);
}
for (int col = 0; col < n; col++) {
turn(0,col,board);
turn(m - 1,col,board);
}
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
if (board[row][col] == 'O') {
board[row][col] = 'X';
}else if (board[row][col] == 'T') {
board[row][col] = 'O';
}
}
}
}
}; | c******e
发帖数: 558 | | b******g
发帖数: 3616 | 3 那个很长的zigzag test case我记得两个月前就有了。你这个解法是不是run time
error而不是time limit exceeded?
应该不是剪枝的问题，而是stack overflow了。因为你的dfs是用递归来做的，数据大
了就不行了。改成用stack的dfs或用queue的bfs就行了。
，T
【在 d********m 的大作中提到】
: 思路是从4个边界分别检测，如果是O就替换为T。最后在整体遍历一次，把O的改为X，T
: 改为O。
: 过不去的那个test case超级长，自己测不了。麻烦各位大侠给看看代码。
: 谢谢先～
: class Solution {
: public:
: void turn (int row, int col, vector> &board) {
: if (row < 0 || row >= board.size() || col < 0 || col >= board[0].
: size() || board[row][col] != 'O' ) {
: return;
| d********m
发帖数: 101 | 4 多谢2位回答！后来改用queue的bfs才能通过
上面的代码在10个月前确实能通过，现在出的新的test case确实runtime error，而不
是time limit exceeded
如果用stack的dfs跟上面的递归会有区别吗？ | b******g
发帖数: 3616 | 5 有区别。用stack的dfs不会造成rum time error，你试下，写个stack DFS也就一分钟
的事情。
recursion的问题在于是消耗call stack，很容易stack overflow。用iteration消耗的
是heap。
【在 d********m 的大作中提到】
: 多谢2位回答！后来改用queue的bfs才能通过
: 上面的代码在10个月前确实能通过，现在出的新的test case确实runtime error，而不
: 是time limit exceeded
: 如果用stack的dfs跟上面的递归会有区别吗？
|
|
