题目：Surrounded Regions
广搜和深搜都能解决，但是LeetCode上使用深搜时会栈溢出
DFS:
<span style="font-size:18px;">/*LeetCode Surrounded Regions * 题目：给定一个字符数组，由'X'和'O'组成，找到所有被x包围的o并将其替换为x * 思路：只要替换被包围的o就行，如果有一个o是边界或者上下左右中有一个是o且这个o不会被替换，则该点也不会被替换 * 从四条边开始，，因为在这4周的一定不是被包围的所以用他们开始找到广搜的队列，如果队列为空，那么就是所有的o都被包围 */package javaTrain;public class Train25 {public static void solve(char[][] board) {long n = board.length;if(n==0) return;long m = board[0].length;for(long i = 0;i < m;i++){//对第一行和最后一行的字符进行广搜bfs(board,0,i);bfs(board,n-1,i);}for(long j = 1;j < n-1;j++){ //对第一列和最后一列的字符进行广搜，去除4条边重复的字符bfs(board,j,0);bfs(board,j,m-1);}for(int i = 0;i < n;i++){for(int j = 0;j < m;j++){if(board[i][j] == 'O') board[i][j] = 'X';//被包围的o需取代else if(board[i][j] == '$') board[i][j] = 'O';//标记的不被包围的o保持原样}}}private static void bfs(char[][] board,int i,int j){long n = board.length;long m = board[0].length;if(i < 0 || i>=n||j<0||j>=m||board[i][j] != 'O') return; //边界的点都不被包围board[i][j] = '$';bfs(board,i-1,j);bfs(board,i,j-1);bfs(board,i+1,j);bfs(board,i,j+1); } public static void main(String args[]){char board[][] = {{'O','X','O'},{'X','O','X'},{'O','X','O'}};solve(board);for(int i = 0;i < board.length;i++){for(int j = 0;j < board[0].length;j++){System.out.print(board[i][j]);}System.out.println();} }}</span>BFS:
<span style="font-size:18px;">// LeetCode, Surrounded Regions// BFS，时间复杂度O(n)，空间复杂度O(n)class Solution {public:void solve(vector<vector<char>> &board) {if (board.empty()) return;const int m = board.size();const int n = board[0].size();for (int i = 0; i < n; i++) {bfs(board, 0, i);bfs(board, m – 1, i);}for (int j = 1; j < m – 1; j++) {bfs(board, j, 0);bfs(board, j, n – 1);}for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (board[i][j] == 'O')board[i][j] = 'X';else if (board[i][j] == '+')board[i][j] = 'O';}private:void bfs(vector<vector<char>> &board, int i, int j) {typedef pair<int, int> state_t;queue<state_t> q;const int m = board.size();const int n = board[0].size();auto is_valid = [&](const state_t &s) {const int x = s.first;const int y = s.second;if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O')return false;return true;};auto state_extend = [&](const state_t &s) {vector<state_t> result;const int x = s.first;const int y = s.second;// 上下左右const state_t new_states[4] = {{x-1,y}, {x+1,y},{x,y-1}, {x,y+1}};for (int k = 0; k < 4; ++k) {if (is_valid(new_states[k])) {// 既有标记功能又有去重功能board[new_states[k].first][new_states[k].second] = '+';result.push_back(new_states[k]);}}return result;};state_t start = { i, j };if (is_valid(start)) {board[i][j] = '+';q.push(start);}while (!q.empty()) {auto cur = q.front();q.pop();auto new_states = state_extend(cur);for (auto s : new_states) q.push(s);}}};</span>
昨晚多几分钟的准备，今天少几小时的麻烦。
