[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 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

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<) return;

        int n=board[].size();

        if(n<) return;

        vector<vector<bool> > flag;

        for(int i=;i<m;i++)    flag.push_back(vector<bool>(n,false));

        for(int i=;i<m;i++){

            for(int j=;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=,m=board.size(),n=board[].size();

        while(now_idx<tmp.size()){

            int now_i = tmp[now_idx].first,now_j = tmp[now_idx].second;

            if(now_i->=&&board[now_i-][now_j]=='O'&&flag[now_i-][now_j]==false){

                tmp.push_back({now_i-,now_j});

                flag[now_i-][now_j]=true;

            }

            if(now_i+<m&&board[now_i+][now_j]=='O'&&flag[now_i+][now_j]==false){

                tmp.push_back({now_i+,now_j});

                flag[now_i+][now_j]=true;

            }

            if(now_j->=&&board[now_i][now_j-]=='O'&&flag[now_i][now_j-]==false){

                tmp.push_back({now_i,now_j-});

                flag[now_i][now_j-]=true;

            }

            if(now_j+<n&&board[now_i][now_j+]=='O'&&flag[now_i][now_j+]==false){

                tmp.push_back({now_i,now_j+});

                flag[now_i][now_j+]=true;

            }

            now_idx++;

        }

        bool canCapture=true;

        now_idx=;

        while(canCapture&&now_idx<tmp.size()){

            int now_i = tmp[now_idx].first,now_j = tmp[now_idx].second;

            if(now_i==||now_i==m-||now_j==||now_j==n-)  canCapture=false;

            now_idx++;

        }

        if(canCapture){

            now_idx=;

            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=;i<board.size();i++){

        copy(board[i].begin(),board[i].end(),ostream_iterator<char>(cout," "));

        cout<<endl;

    }

    return ;

}

改进：

　　注意到O 不能修改的是与边相连的时候，那么便改变下过程，从边开始，找出全部不能够变化的O，然后其余的O 变化，这样时间快很多。这个就不写了。

discuss 中提到并查集，看了一下，也就是讲全部的O 找出来，相连的划分成一个集合中，集合内的元素链表表示，一个接一个，这样避免了重复，而我实现是通过后台标记，并查集的时间其实更长，因为是单项链表的实现。或许有更好的实现，例如1-n 树表示，不过选用那个作为根节点，好像这题目不是很好用。

巴特西

[LeetCode] Surrounded Regions 广度搜索

最新文章

热门文章