[leetcode] 130. Surrounded Regions

[leetcode] 130. Surrounded Regions

Description

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

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

Example:

X X X XX O O XX X O XX O X X

After running your function, the board should be:

X X X XX X X XX X X XX O X X

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

分析

题目的意思是：如果O四周都是X的话，那么用X覆盖O，求最终的状态。

遍历矩阵的四条边，如果出现O字符，我们把O替换为Z，然后沿着这个点深度优先遍历找与之相邻的O，同样置为Z，最后我们把Z的位置用O替换，把原来的O用X替换

代码

class Solution {public: void solve(vector>& board) { if(board.empty()||board.size()==0){ return ; } int m=board.size(); int n=board[0].size(); for(int i=0;i>& board,int x,int y,int m,int n){ int dx[]={-1,0,0,1}; int dy[]={0,-1,1,0}; for(int i=0;i<4;i++){ int x1=x+dx[i]; int y1=y+dy[i]; if(!isOut(x1,y1,m,n)&&board[x1][y1]=='O'){ board[x1][y1]='Z'; dfs(board,x1,y1,m,n); } } } bool isOut(int x,int y,int m,int n){ return x<0||x>=m||y<0||y>=n; }};

参考文献

​​Leetcode—Surrounded Regions​​​​[编程题]surrounded-regions​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。