【面试经典 150 | 图】被围绕的区域

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：深搜
- 方法二：广搜
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【图】【深搜】【广搜】

题目来源

130. 被围绕的区域

解题思路

标记为 A

我们从网格的边缘（第一行、最后一行、第一列、最后一列）的 ‘O’ 字符出发将所有与之相连的 ‘O’ 都标记成一种全新的字符，不妨标记为 ‘A’。

这个过程可以通过深搜，广搜以及并查集的方法实现。

最后遍历修改后的网格，将没有被修改的 ‘O’ 更改成字符 ‘X’。因为在 标记为 A 的过程中，有部分 ‘O’ 没有被修改，说明这部分的 ‘O’ 被 ‘X’ 包围，因为可以直接修改成 ‘X’。

方法一：深搜

代码

class Solution {
private:
    const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
	void solve(vector<vector<char>>& board) {
		int m = board.size(), n = board[0].size();
		for (int i = 0; i < m; ++i) {
			dfs(board, m, n, i, 0);
			dfs(board, m, n, i, n - 1);
		}

		for (int i = 1; i < n - 1; ++i) {
			dfs(board, m, n, 0, i);
			dfs(board, m, n, m - 1, i);
		}

		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (board[i][j] == 'A') {
					board[i][j] = 'O';
				}
				else if (board[i][j] == 'O') {
					board[i][j] = 'X';
				}	
			}
		}

	}

	void dfs(vector<vector<char>>& board, int m, int n, int i, int j) {
		if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O')
			return;

		board[i][j] = 'A';

        for (int k = 0; k < 4; ++k) {
            int nx = i + dirs[k][0];
            int ny = j + dirs[k][1];
            dfs(board, m, n, nx, ny);
        }
	}
};

复杂度分析

时间复杂度： $O (mn)$ ， $m$ 和 $n$ 分别为网格的行数和列数。

空间复杂度： $O (mn)$ 。

方法二：广搜

代码

class Solution {
private:
	vector<int> direction{ -1, 0, 1, 0, -1 };
public:
	void solve(vector<vector<char>>& board) {
		int m = board.size(), n = board[0].size();
		queue<pair<int, int>> que;
		for (int i = 0; i < m; ++i) {
			if (board[i][0] == 'O') {
				que.emplace(i, 0);
				board[i][0] = 'A';
			}

			if (board[i][n - 1] == 'O') {
				que.emplace(i, n-1);
				board[i][n - 1] = 'A';
			}
		}

		for (int i = 1; i < n - 1; ++i) {
			if (board[0][i] == 'O') {
				que.emplace(0, i);
				board[0][i] = 'A';
			}

			if (board[m - 1][i] == 'O') {
				que.emplace(m - 1, i);
				board[m - 1][i] = 'A';
			}
		}

		while (!que.empty()) {
			int x = que.front().first, y = que.front().second;
			que.pop();
			for (int k = 0; k < 4; ++k) {
				int r = x + direction[k], c = y + direction[k+1];
				if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O')
					continue;
				que.emplace(r, c);
				board[r][c] = 'A';
			}
		}
		
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (board[i][j] == 'A') {
					board[i][j] = 'O';
				}
				else if (board[i][j] == 'O') {
					board[i][j] = 'X';
				}
			}
		}
	}
};

复杂度分析

时间复杂度： $O (mn)$ ， $m$ 和 $n$ 分别为网格的行数和列数。