LeetCode Surrounded Regions

LeetCode Surrounded Regions

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.

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

给定一个board,要求把其中被X包围的O也改为X,这里的包围必须四周全都有X

开始的想法是,这个问题类似于找岛屿的问题,可以用BFS/DFS或者并查集,但是感觉不太好弄,比如虽然并查集能找到所有岛屿,但是要区分全包围和半包围还是有点麻烦。

查看讨论区,解法很巧妙。半包围的O肯定出现在边缘,所以我们先从边缘的O开始DFS,把所有半包围的O改为一个其他的字符,比如'1'。这样之后,剩余的所有O肯定是被X全包围的,而那些被标记为'1'的,则是原来被半包围的'O'。所以最后,我们遍历整个board,遇到'O'直接改为'X'就好,遇到'1',则改回原来的'O'。直接O(1)空间复杂度就搞定了,不错。

代码如下:

vector<vector<int>> dirs = { {1,0},{-1,0},{0,1},{0,-1} };

class Solution {
private:
	int m, n;
	bool isOk(int x, int y) {
		return x >= 0 && x < m&&y >= 0 && y < n;
	}
	void dfs(vector<vector<char>>& board, int x, int y) {
		board[x][y] = '1';
		for (int i = 0; i < dirs.size(); ++i) {
			int u = x + dirs[i][0], v = y + dirs[i][1];
			if (isOk(u, v) && board[u][v] == 'O') dfs(board, u, v);
		}
	}
public:
	void solve(vector<vector<char>>& board) {
		if (board.empty() || board[0].empty())return;
		m = board.size(), n = board[0].size();
		for (int i = 0; i < m; ++i) {
			if (board[i][0] == 'O') dfs(board, i, 0);
			if (board[i][n - 1] == 'O') dfs(board, i, n - 1);
		}
		for (int j = 0; j < n; ++j) {
			if (board[0][j] == 'O') dfs(board, 0, j);
			if (board[m - 1][j] == 'O') dfs(board, m - 1, j);
		}
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (board[i][j] == 'O')board[i][j] = 'X';
				else if (board[i][j] == '1')board[i][j] = 'O';
			}
		}
	}
};

本代码提交AC,用时13MS。

Leave a Reply

Your email address will not be published. Required fields are marked *