2014-05-06 14:04
原题：
given an 2D matrix M, is filled either using X or O, you need to find the region which is filled by O and surrounded by X
and fill it with X. example : X X X X X
X X O O X
X X O O X
O X X X X Answer : X X X X X
X X X X X
X X X X X
O X X X X example : X X X X X
X X O O X
X X O O O
O X X X X answer :
X X X X X
X X O O X
X X O O O
O X X X X
题目：参见Leetcode题目Surrounded Regions。
解法：题解位于LeetCode - Surrounded Regions。
代码：
// http://www.careercup.com/question?id=5727310284062720
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std; class Solution {
public:
void solve(vector<vector<char> > &board) {
// Should n or m be smaller than 3, there'll be no captured region.
n = (int)board.size();
if (n < ) {
return;
} m = (int)board[].size();
if (m < ) {
return;
} int i, j; // if an 'O' is on the border, all of its connected 'O's are not captured.
// so we scan the border and mark those 'O's as free. // the top row
for (j = ; j < m; ++j) {
if (board[][j] == 'O') {
check_region(board, , j);
}
} // the bottom row
for (j = ; j < m; ++j) {
if (board[n - ][j] == 'O') {
check_region(board, n - , j);
}
} // the left column
for (i = ; i < n - ; ++i) {
if (board[i][] == 'O') {
check_region(board, i, );
}
} // the right column
for (i = ; i < n - ; ++i) {
if (board[i][m - ] == 'O') {
check_region(board, i, m - );
}
} // other unchecked 'O's are all captured
for (i = ; i < n; ++i) {
for (j = ; j < m; ++j) {
if (board[i][j] == '#') {
// free 'O's
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
// captured 'O's
board[i][j] = 'X';
}
}
}
}
private:
int n, m; void check_region(vector<vector<char> > &board, int startx, int starty) {
if (startx < || startx > n - || starty < || starty > m - ) {
return;
}
if (board[startx][starty] == 'O') {
board[startx][starty] = '#';
check_region(board, startx - , starty);
check_region(board, startx + , starty);
check_region(board, startx, starty - );
check_region(board, startx, starty + );
}
}
}; int main()
{
int n, m;
int i, j;
string str;
vector<vector<char> > board;
Solution sol; while (cin >> n >> m && (n > && m > )) {
board.resize(n);
for (i = ; i < n; ++i) {
cin >> str;
board[i].resize(m);
for (j = ; j < m; ++j) {
board[i][j] = str[j];
}
}
sol.solve(board);
for (i = ; i < n; ++i) {
for (j = ; j < m; ++j) {
cout << board[i][j];
}
cout << endl;
} for (i = ; i < n; ++i) {
board[i].clear();
}
board.clear();
} return ;
}