Surrounded Regions --leetcode

本文主要是介绍Surrounded Regions --leetcode，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

https://oj.leetcode.com/problems/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在四条边上。因此可以利用flood fill算法对四条边上的O进行处理，先将O改成其他的字母，这样就不需要记录已经访问过的点了。 这个题目leetcode 里面如果利用DFS递归算法的话，会出现runtime error，应该是对于函数的递归调用有限制，因此改为BFS就可以了。

class Solution {
public:struct point{int x;int y;};void solve(vector<vector<char> > &board){int isx = board.size();if(isx <=0 )return ;int isy = board[0].size();for (int i =0; i < isy; i ++){presolve(board,0,i);presolve(board,isx-1,i);}for (int i =1; i < isx; i ++){presolve(board,i,0);presolve(board,i,isy-1);}for (int i =0;i < isx;i ++){for (int j = 0;j < isy;j ++){if(board[i][j] == 'O'){board[i][j] = 'X';}else if(board[i][j] == 't'){board[i][j] = 'O';}}}}//use BFS DFS will run errorvoid presolve(vector<vector<char> > &board,int x,int y){if(board[x][y] != 'O') return ;queue<point> pq;point pt;pt.x = x;pt.y = y;pq.push(pt);point tp;while (!pq.empty()){tp = pq.front();pq.pop();if(board[tp.x][tp.y] == 'O'){board[tp.x][tp.y] = 't';if(tp.x-1 >= 0 && board[tp.x-1][tp.y] == 'O'){pt.x = tp.x-1;pt.y = tp.y;pq.push(pt);}if(tp.x+1 < board.size() && board[tp.x+1][tp.y] == 'O'){pt.x = tp.x+1;pt.y = tp.y;pq.push(pt);}if(tp.y-1 >= 0 && board[tp.x][tp.y-1] == 'O'){pt.x = tp.x;pt.y = tp.y-1;pq.push(pt);}if(tp.y+1 >= 0 && board[tp.x][tp.y+1] == 'O'){pt.x = tp.x;pt.y = tp.y+1;pq.push(pt);}}}return ;}
};

这篇关于Surrounded Regions --leetcode的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---