首页 > 代码库 > [LeetCode] Surrounded Regions 广度搜索
[LeetCode] 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 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
Hide Tags
Breadth-first Search 题目是给定一个char 矩阵，将被包括的O 标记为X。
思路：
遍历整个矩阵，如果遇到O 那么便找出全部与其相连的O，然后判断这个是否需要变换。
这样的实现就是判断麻烦一些，而且会有重复判断，因为需要先找出全部的相连O，再遍历一次判断，然后遍历修改，操作有重复了，下面是我写的代码：
#include <vector>#include <iostream>#include <iterator>using namespace std;class Solution {public: void solve(vector<vector<char> > &board) { int m=board.size(); if(m<2) return; int n=board[0].size(); if(n<2) return; vector<vector<bool> > flag; for(int i=0;i<m;i++) flag.push_back(vector<bool>(n,false)); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(board[i][j]==‘X‘) flag[i][j]=true; if(board[i][j]==‘O‘&&flag[i][j]==false) help_f(i,j,board,flag); } } return ; } void help_f(int i,int j,vector<vector<char> > &board,vector<vector<bool> > &flag) {// cout<<"Azhu"<<endl; vector<pair<int,int> > tmp; tmp.push_back({i,j}); flag[i][j]=true; int now_idx=0,m=board.size(),n=board[0].size(); while(now_idx<tmp.size()){ int now_i = tmp[now_idx].first,now_j = tmp[now_idx].second; if(now_i-1>=0&&board[now_i-1][now_j]==‘O‘&&flag[now_i-1][now_j]==false){ tmp.push_back({now_i-1,now_j}); flag[now_i-1][now_j]=true; } if(now_i+1<m&&board[now_i+1][now_j]==‘O‘&&flag[now_i+1][now_j]==false){ tmp.push_back({now_i+1,now_j}); flag[now_i+1][now_j]=true; } if(now_j-1>=0&&board[now_i][now_j-1]==‘O‘&&flag[now_i][now_j-1]==false){ tmp.push_back({now_i,now_j-1}); flag[now_i][now_j-1]=true; } if(now_j+1<n&&board[now_i][now_j+1]==‘O‘&&flag[now_i][now_j+1]==false){ tmp.push_back({now_i,now_j+1}); flag[now_i][now_j+1]=true; } now_idx++; } bool canCapture=true; now_idx=0; while(canCapture&&now_idx<tmp.size()){ int now_i = tmp[now_idx].first,now_j = tmp[now_idx].second; if(now_i==0||now_i==m-1||now_j==0||now_j==n-1) canCapture=false; now_idx++; } if(canCapture){ now_idx=0; while(now_idx<tmp.size()){ int now_i = tmp[now_idx].first,now_j = tmp[now_idx].second; board[now_i][now_j]=‘X‘; now_idx++; } } return ; }};int main(){ vector<vector<char> > board{ {{‘X‘,‘X‘,‘X‘,‘O‘}}, {{‘X‘,‘O‘,‘O‘,‘X‘}}, {{‘X‘,‘X‘,‘X‘,‘X‘}}, {{‘X‘,‘O‘,‘O‘,‘X‘}} }; Solution sol; sol.solve(board); for(int i=0;i<board.size();i++){ copy(board[i].begin(),board[i].end(),ostream_iterator<char>(cout," ")); cout<<endl; } return 0;}
改进：
注意到O 不能修改的是与边相连的时候，那么便改变下过程，从边开始，找出全部不能够变化的O，然后其余的O 变化，这样时间快很多。这个就不写了。
discuss 中提到并查集，看了一下，也就是讲全部的O 找出来，相连的划分成一个集合中，集合内的元素链表表示，一个接一个，这样避免了重复，而我实现是通过后台标记，并查集的时间其实更长，因为是单项链表的实现。或许有更好的实现，例如1-n 树表示，不过选用那个作为根节点，好像这题目不是很好用。
[LeetCode] Surrounded Regions 广度搜索
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。