avatar
问surrounded region# JobHunting - 待字闺中
G*n
1
用很普通的dfs,leetcode oj就是过不去,
Last executed input: OOOOOOOOOOOO... XXXXXXX.... 交替出现的例子过不去。
求解。。
avatar
b*t
2
几个月前写的
现在我自己也看不懂了
class Solution {
public:
void solve(vector > &board) {

vector > visited=board;
vector > listOfPoints;
for(int i=0;ifor(int j=0;j{
listOfPoints.clear();
stack > candidatePoints;
if (visited[i][j]=='O')
{
candidatePoints.push(pair(i,j));
bool test=false;
while(!candidatePoints.empty())
{
pair p =candidatePoints.top();
int pi=p.first;
int pj=p.second;
visited[pi][pj]='X';
listOfPoints.push_back(p);
candidatePoints.pop();
if ( ( pi==board.size()-1) || (pj==board[0].size()-1) ||
(pi==0) || (pj==0) )
test=true;
if ( (pi+1candidatePoints.push(pair(pi+1,pj));
if ( (pj+1candidatePoints.push(pair(pi,pj+1));
if ( (pi-1>=0) && (visited[pi-1][pj]=='O') )
candidatePoints.push(pair(pi-1,pj));
if ( (pj-1>=0) && (visited[pi][pj-1]=='O') )
candidatePoints.push(pair(pi,pj-1));
}

if (!test)
for(int s=0;sboard[listOfPoints[s].first][listOfPoints[s].second]='X';
}
}

}
};

【在 G******n 的大作中提到】
: 用很普通的dfs,leetcode oj就是过不去,
: Last executed input: OOOOOOOOOOOO... XXXXXXX.... 交替出现的例子过不去。
: 求解。。

avatar
y*n
3
哈哈,和我一样,经常自己的代码都看不懂了。。
avatar
c*6
4
稍微修改下 dfs可以过
avatar
G*n
5
代码贴上来。
void DFS(vector > &board, int i, int j, int m, int n){
if (i < 0 || j < 0|| i >= m || j >= n || board[i][j] != 'O')
return;

board[i][j] = 'P';
DFS(board, i+1, j, m, n);
DFS(board, i-1, j, m, n);
DFS(board, i, j+1, m, n);
DFS(board, i, j-1, m, n);
}

void solve(vector> &board) {
if (board.empty())
return;
int m = board.size(), n = board[0].size();

for(int i = 0; i < m; i++){
DFS(board, i, 0, m, n);
DFS(board, i, n-1, m, n);
}
for(int j = 0; j < n; j++){
DFS(board, 0, j, m, n);
DFS(board, m-1, j, m, n);
}

for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++){
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == 'P') board[i][j] = 'O';
}
}
};
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。