leetcode 130. Surrounded Regions

Bertha 。 2022-07-28 00:15 123阅读 0赞

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

这题比较简单，就是XXOO游戏嘛。思路是找到处于边界的suoyou‘O’的连通区域，做个记号，然后剩下的'O'就全部是被‘X’包围的了，置为'X'即可。

说句题外话，XXOO里的O到底是O呢还是0呢。要弄明白，否则容易掉坑

class Solution {
    public:
    	void solve(vector<vector<char>>& board) {
    		if (board.empty())
    			return;
    		if (board[0].empty())
    			return;
    		if (board.size() < 3 || board[0].size() < 3)
    			return;
    		for (int k = 0; k < 2; k++)
    		{
    			int col = k == 0 ? 0 : board[0].size() - 1;
    			for (int i = 0; i < board.size(); i++)
    			{
    				if (board[i][col] == 'O')
    				{
    					vector<pair<int, int>>que;//pair<int,int>(x,y)
    					board[i][col] = '1';
    					que.push_back(pair<int, int>(col, i));
    					while (!que.empty())
    					{
    						vector<pair<int, int>>newque;
    						for (int i = 0; i < que.size(); i++)
    						{
    							if (que[i].first - 1 >= 0 && board[que[i].second][que[i].first - 1] == 'O')
    							{
    								newque.push_back(pair<int, int>(que[i].first - 1, que[i].second));
    								board[que[i].second][que[i].first - 1] = '1';
    							}
    							if (que[i].first + 1 < board[0].size() && board[que[i].second][que[i].first + 1] == 'O')
    							{
    								newque.push_back(pair<int, int>(que[i].first + 1, que[i].second));
    								board[que[i].second][que[i].first + 1] = '1';
    							}
    							if (que[i].second - 1 >= 0 && board[que[i].second - 1][que[i].first] == 'O')
    							{
    								newque.push_back(pair<int, int>(que[i].first, que[i].second - 1));
    								board[que[i].second - 1][que[i].first ] = '1';
    							}
    							if (que[i].second + 1 < board.size() && board[que[i].second + 1][que[i].first] == 'O')
    							{
    								newque.push_back(pair<int, int>(que[i].first, que[i].second + 1));
    								board[que[i].second + 1][que[i].first] = '1';
    							}
    						}
    						que = newque;
    					}
    				}
    			}
    		}
    		for (int k = 0; k < 2; k++)
    		{
    			int row = k == 0 ? 0 : board.size() - 1;
    			for (int i = 0; i < board[0].size(); i++)
    			{
    				if (board[row][i] == 'O')
    				{
    					vector<pair<int, int>>que;
    					board[row][i] = '1';
    					que.push_back(pair<int, int>(i,row));
    					while (!que.empty())
    					{
    						vector<pair<int, int>>newque;
    						for (int i = 0; i < que.size(); i++)
    						{
    							if (que[i].first - 1 >= 0 && board[que[i].second][que[i].first - 1] == 'O')
    							{
    								newque.push_back(pair<int, int>(que[i].first - 1, que[i].second));
    								board[que[i].second][que[i].first - 1] = '1';
    							}
    							if (que[i].first + 1 < board[0].size() && board[que[i].second][que[i].first + 1] == 'O')
    							{
    								newque.push_back(pair<int, int>(que[i].first + 1, que[i].second));
    								board[que[i].second][que[i].first + 1] = '1';
    							}
    							if (que[i].second - 1 >= 0 && board[que[i].second - 1][que[i].first] == 'O')
    							{
    								newque.push_back(pair<int, int>(que[i].first,que[i].second - 1));
    								board[que[i].second-1][que[i].first] = '1';
    							}
    							if (que[i].second + 1 < board.size() && board[que[i].second + 1][que[i].first] == 'O')
    							{
    								newque.push_back(pair<int, int>(que[i].first,que[i].second + 1));
    								board[que[i].second + 1][que[i].first] = '1';
    							}
    						}
    						que = newque;
    					}
    				}
    			}
    		}
    		for (int i = 1; i < board.size() - 1; i++)
    			for (int j = 1; j < board[0].size() - 1; j++)
    			{
    				if (board[i][j] == 'O')
    					board[i][j] = 'X';
    			}
    		for (int i = 0; i < board.size(); i++)
    			for (int j = 0; j < board[0].size(); j++)
    			{
    				if (board[i][j] == '1')
    					board[i][j] = 'O';
    			}
    	}
    };

accepted