LeetCode130:Surrounded Regions

题目:

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X
解题思路:
首先在遍历最外面的四条边,如果遇到O,则表示有出路,这时,以找到的O点为起点,采用BFS或DFS进行遍历,找到与其他与该O点相邻的O点,然后将其置为*,第一步处理完后,再重新遍历整个矩阵,将为*的点置为O,为O的点置为X即可。
实现代码:
#include <iostream>
#include <vector>
#include <queue>
using namespace std; /*
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be: X X X X
X X X X
X X X X
X O X X
*/ class Solution {
public:
void solve(vector<vector<char>> &board) {
if(board.empty() || board[0].empty())
return ;
int rows = board.size();
int cols = board[0].size();
for(int i = 0; i < rows; i++)
{
if(board[i][0] == 'O')
bfs(i, 0, board, rows, cols);
if(board[i][cols-1] == 'O')
bfs(i, cols-1, board, rows, cols);
}
for(int j = 0; j < cols; j++)
{
if(board[0][j] == 'O')
bfs(0, j, board, rows, cols);
if(board[rows-1][j] == 'O')
bfs(rows-1, j, board, rows, cols);
} for(int i = 0; i < rows; i++)
for(int j = 0; j < cols; j++)
if(board[i][j] == 'O')
board[i][j] = 'X';
else if(board[i][j] == '*')
board[i][j] = 'O'; } void bfs(int i, int j, vector<vector<char>> &board, int rows, int cols)
{
queue<pair<int, int>> qu;
qu.push(make_pair(i, j));
while(!qu.empty())
{
pair<int, int> p = qu.front();
qu.pop();
int ii = p.first;
int jj = p.second;
if(ii < 0 || ii >= rows || jj < 0 || jj >= cols || board[ii][jj] != 'O')
continue;
board[ii][jj] = '*';
qu.push(make_pair(ii, jj-1));
qu.push(make_pair(ii, jj+1));
qu.push(make_pair(ii-1, jj));
qu.push(make_pair(ii+1, jj)); }
}
}; int main(void)
{
return 0;
}
上一篇:C# 世界坐标 页面坐标 PageUnit PageScale


下一篇:svn 提交代码报错