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区域，如果这个区域不与边界接触则是被包围区域，但是这种判断要等到dfs完成才能知道是否是被包围区域，所以需要再一次dfs来将这些点变成'X'。所以这样的复杂度太高，Judge Large超时。这个版本的代码包括下面的dfs和changeBoard，以及Solve中被注释掉的部门代码；后来参考了网上的一个代码，将思路转变为先对不被包围的区域做标记'C'，然后再遍历一遍按要求修改。这样就避免了做两遍深度搜索。
代码如下：（有点难看，见谅……）
//
// SurroundedRegions.cpp
// SJMcode
//
// Created by Jiamei Shuai on 13-8-30.
// Copyright (c) 2013年 Jiamei Shuai. All rights reserved.
// #include <iostream>
#include <vector>
#include <assert.h>
using namespace std; class Solution {
public: void dfs2(vector<vector<char>> &board, int i, int j)
{
if(i > board.size()- || i < || j > board[].size()- || j < )
return; if(board[i][j] == 'O')
{
board[i][j] = 'C';
dfs2(board, i+, j);
dfs2(board, i-, j);
dfs2(board, i, j-);
dfs2(board, i, j+);
} } bool dfs(vector<vector<char>> &board, int i, int j, int height, int width, vector<vector<int>> &isVis, bool &flag) // working but too slow
{
//if(board[i][j] == 'X') return true; if(i == height- || i == || j == width- || j == )
flag = false; // 'o' touch the border: means this block cannot be the answer isVis[i][j] = ; if(i >= && !isVis[i-][j] && board[i-][j] == 'O')
{
dfs(board, i-, j, height, width, isVis, flag); //上
}
if(i < (int)board.size()- && !isVis[i+][j] && board[i+][j] == 'O')
{
dfs(board, i+, j, height, width, isVis, flag); //下
}
if(j >= && !isVis[i][j-] && board[i][j-] == 'O')
{
dfs(board, i, j-, height, width, isVis, flag); //左
}
if(j < (int)board[].size() && !isVis[i][j+] && board[i][j+] == 'O')
{
dfs(board, i, j+, height, width, isVis, flag); //右
} return flag;
} void changeBoard(vector<vector<char>> &board, int i, int j) // working but too slow
{
vector<int> queue;
board[i][j] = 'X';
assert(i > && i < board.size()- && j > && j < board[].size()-);
if(board[i-][j] == 'O')
changeBoard(board, i-, j);
if(board[i+][j] == 'O')
changeBoard(board, i+, j);
if(board[i][j-] == 'O')
changeBoard(board, i, j-);
if(board[i][j+] == 'O')
changeBoard(board, i, j+);
} void solve(vector<vector<char>> &board) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int height = (int)board.size();
if(height == ) return;
int width = (int)board[].size(); // vector<int> temp(width, 0);
//
// vector<vector<int>> isVis(height, temp);
// bool flag = true;
//
// for(int i = 0; i < height; i++)
// {
// for(int j = 0; j < width; j++)
// {
// if(board[i][j] == 'O' && !isVis[i][j])
// {
// flag = true;
// if(dfs(board, i, j, height, width, isVis, flag)) // surround regions
// {
// changeBoard(board, i, j); // Find surround region directly may cause runtime error
// }
// }
// }
// } // Change my strategy to mark unsurrounded regions for(int i = ; i < height; i++)
{
dfs2(board, i, );
dfs2(board, i, width-);
} for(int j = ; j < width; j++)
{
dfs2(board, , j);
dfs2(board, height-, j);
} for(int i = ; i < height; i++)
{
for(int j = ; j < width; j++)
{
if(board[i][j] == 'O') board[i][j] = 'X';
if(board[i][j] == 'C') board[i][j] = 'O';
}
} // print result
for(int i = ; i < height; i++)
{
for(int j = ; j < width; j++)
{
cout << board[i][j] << ' ';
}
cout << endl;
} } }; int main()
{
vector<vector<char>> board{{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}}; Solution sln;
sln.solve(board); return ;
}
此外，提交的代码是不能有输出语句的，否则会报Internal Error。
BFS也可以做：http://blog.sina.com.cn/s/blog_b9285de20101j1dt.html