问surrounded region - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问surrounded region

问surrounded region# JobHunting - 待字闺中

G*n2014-07-20 07:07

1 楼

用很普通的dfs，leetcode oj就是过不去，
Last executed input: OOOOOOOOOOOO... XXXXXXX.... 交替出现的例子过不去。
求解。。

b*t2014-07-20 07:07

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.... 交替出现的例子过不去。
: 求解。。

y*n2014-07-20 07:07

3 楼

哈哈，和我一样，经常自己的代码都看不懂了。。

c*62014-07-20 07:07

4 楼

稍微修改下 dfs可以过

G*n2014-07-20 07:07

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';
}
}
};