[leetcodeブラシシリーズ]Surrounded Regions
2113 ワード
囧,この問題はdfsで私はreしました.爆桟のはずです.それでbfsに変えて過ぎた
const int MAXN = 1000 + 10;
const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};
int n, m;
bool vis[MAXN][MAXN];
void bfs(int r, int c, vector<vector<char> > & board){
queue<pair<int, int> > q;
q.push(make_pair(r, c));
vis[r][c] = 1;
while(!q.empty()){
r = q.front().first;
c = q.front().second;
q.pop();
for(int p = 0; p < 4; ++ p){
int nr = r + dx[p];
int nc = c + dy[p];
if(nr >= 0 && nr < n)
if(nc >= 0 && nc < m)
if(!vis[nr][nc])
if(board[nr][nc] == 'O'){
vis[nr][nc] = 1;
q.push(make_pair(nr, nc));
}
}
}
}
class Solution {
public:
void solve(vector<vector<char>> &board) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(board.size() <= 0 || board[0].size() <= 0)
return;
memset(vis, 0x00, sizeof(vis));
n = board.size();
m = board[0].size();
for(int i = 0; i < m; ++ i)
if(board[0][i] == 'O')
if(!vis[0][i])
bfs(0, i, board);
for(int i = 0; i< m; ++ i)
if(board[n - 1][i] == 'O')
if(!vis[n - 1][i])
bfs(n - 1, i, board);
for(int i = 0; i < n; ++ i)
if(board[i][0] == 'O')
if(!vis[i][0])
bfs(i, 0, board);
for(int i = 0; i < n; ++ i)
if(board[i][m - 1] == 'O')
if(!vis[i][m - 1])
bfs(i, m - 1, board);
for(int i = 0; i < n; ++ i)
for(int j = 0; j < m; ++ j)
if(board[i][j] == 'O')
if(!vis[i][j])
board[i][j] = 'X';
}
};