创新创意产品设计作品_潍坊大型网站建设_在线推广企业网站的方法有哪些_云南网络推广seo代理公司

力扣第130题：被围绕的区域 - C语言解法

题目描述

给定一个二维的矩阵，包含 'X' 和 'O' 两种字符。一个被 'X' 围绕的区域被称为“封闭区域”，其中 'O' 字符完全被 'X' 字符包围，不与边界相连。

你需要 改变所有被围绕的 'O' 为 'X'。同时，所有与边界相连的 'O' 不会被改变。

注意：

• 你需要修改输入的二维矩阵，并且不返回任何东西。
• 一个被围绕的 'O' 仅指的是不与边界 'O' 相连的 'O'，而与边界 'O' 相连的 'O' 不会被修改。

示例 1：

输入：
X X X X
X O O X
X X O X
X O X X输出：
X X X X
X X X X
X X X X
X O X X

示例 2：

输入：
O O O O
O X O X
O X O X
O O O O输出：
O O O O
O X O X
O X O X
O O O O

解题思路

这个问题可以通过 深度优先搜索（DFS） 或 广度优先搜索（BFS） 来解决。关键在于区分哪些 'O' 是被围绕的，哪些是与边界相连的。

1. 思路分析

1. 标记与边界相连的 'O'：

   • 从边界开始，遍历所有的 'O'，并通过 DFS 或 BFS 来标记这些 'O'。这些 'O' 不应该被修改。
   • 使用一个辅助矩阵或直接修改原矩阵，将与边界相连的 'O' 标记为一个特定值，比如 '#'。

2. 修改被围绕的区域：

   • 遍历整个矩阵，将所有未标记的 'O' 改为 'X'，这些 'O' 都是被围绕的。
   • 将标记为 '#' 的 'O' 重新改回 'O'，因为这些 'O' 是与边界相连的。

2. 时间复杂度和空间复杂度

• 时间复杂度：$O(m\times n)$，其中 $m$ 和 $n$ 分别是矩阵的行数和列数。我们需要遍历整个矩阵进行标记和修改。
• 空间复杂度：$O(m\times n)$，在最坏的情况下，需要额外的空间来存储标记。

---

C语言代码实现

#include <stdio.h>
#include <stdlib.h>#define ROWS 4
#define COLS 4// 深度优先搜索（DFS）函数
void dfs(char** board, int i, int j, int rows, int cols) {// 边界检查if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] != 'O') {return;}// 标记当前节点board[i][j] = '#';  // 临时标记，表示此'O'不被修改// 递归遍历四个方向dfs(board, i+1, j, rows, cols);  // 向下dfs(board, i-1, j, rows, cols);  // 向上dfs(board, i, j+1, rows, cols);  // 向右dfs(board, i, j-1, rows, cols);  // 向左
}// 主函数：修改矩阵中的'O'为'X'
void solve(char** board, int boardSize, int* boardColSize) {if (board == NULL || boardSize == 0 || *boardColSize == 0) {return;}int rows = boardSize;int cols = *boardColSize;// 从边界出发，标记所有与边界相连的'O'为'#'for (int i = 0; i < rows; i++) {if (board[i][0] == 'O') {dfs(board, i, 0, rows, cols);  // 第一列}if (board[i][cols - 1] == 'O') {dfs(board, i, cols - 1, rows, cols);  // 最后一列}}for (int j = 0; j < cols; j++) {if (board[0][j] == 'O') {dfs(board, 0, j, rows, cols);  // 第一行}if (board[rows - 1][j] == 'O') {dfs(board, rows - 1, j, rows, cols);  // 最后一行}}// 遍历整个矩阵，进行最后的修改for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (board[i][j] == 'O') {board[i][j] = 'X';  // 被围绕的'O'改为'X'} else if (board[i][j] == '#') {board[i][j] = 'O';  // 与边界相连的'O'恢复}}}
}int main() {// 示例1：创建二维矩阵char* board1[ROWS] = {(char[]){'X', 'X', 'X', 'X'},(char[]){'X', 'O', 'O', 'X'},(char[]){'X', 'X', 'O', 'X'},(char[]){'X', 'O', 'X', 'X'}};int colSize1 = COLS;solve(board1, ROWS, &colSize1);// 输出修改后的矩阵for (int i = 0; i < ROWS; i++) {for (int j = 0; j < COLS; j++) {printf("%c ", board1[i][j]);}printf("\n");}// 示例2：创建二维矩阵char* board2[ROWS] = {(char[]){'O', 'O', 'O', 'O'},(char[]){'O', 'X', 'O', 'X'},(char[]){'O', 'X', 'O', 'X'},(char[]){'O', 'O', 'O', 'O'}};int colSize2 = COLS;solve(board2, ROWS, &colSize2);// 输出修改后的矩阵for (int i = 0; i < ROWS; i++) {for (int j = 0; j < COLS; j++) {printf("%c ", board2[i][j]);}printf("\n");}return 0;
}

---

代码解析

1. dfs 函数

void dfs(char** board, int i, int j, int rows, int cols) {if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] != 'O') {return;}board[i][j] = '#';  // 临时标记，表示此'O'不被修改dfs(board, i+1, j, rows, cols);  // 向下dfs(board, i-1, j, rows, cols);  // 向上dfs(board, i, j+1, rows, cols);  // 向右dfs(board, i, j-1, rows, cols);  // 向左
}

• 该函数采用 DFS 深度优先搜索的方式，递归地将与边界相连的 'O' 标记为 '#'。
• 通过递归调用，将所有与边界相连的 'O' 标记，确保不会被修改为 'X'。

2. solve 函数

void solve(char** board, int boardSize, int* boardColSize) {if (board == NULL || boardSize == 0 || *boardColSize == 0) {return;}int rows = boardSize;int cols = *boardColSize;// 从边界出发，标记所有与边界相连的'O'为'#'for (int i = 0; i < rows; i++) {if (board[i][0] == 'O') {dfs(board, i, 0, rows, cols);  // 第一列}if (board[i][cols - 1] == 'O') {dfs(board, i, cols - 1, rows, cols);  // 最后一列}}for (int j = 0; j < cols; j++) {if (board[0][j] == 'O') {dfs(board, 0, j, rows, cols);  // 第一行}if (board[rows - 1][j] == 'O') {dfs(board, rows - 1, j, rows, cols);  // 最后一行}}// 遍历整个矩阵，进行最后的修改for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (board[i][j] == 'O') {board[i][j] = 'X';  // 被围绕的'O'改为'X'} else if (board[i][j] == '#') {board[i][j] = 'O';  // 与边界相连的'O'恢复}}}
}

• 该函数通过遍历矩阵的边界，对与边界相连的 'O' 进行标记。
• 之后，遍历整个矩阵，将未标记的 'O' 改为 'X'，将标记为 '#' 的 'O' 恢复为 'O'。

3. main 函数

int main() {// 示例1和示例2的输入输出处理
}

• 在 main 函数中，定义了两个示例矩阵，并通过调用 solve 函数对其进行修改。最后输出修改后的矩阵。

---

总结

本题通过深度优先搜索（DFS）对矩阵中与边界相连的 'O' 进行标记，确保它们不会被改变。通过这种方式，我们有效地解决了被围绕的区域修改问题。

关键点：

• 使用 DFS 来标记与边界相连的 'O'。
• 遍历矩阵，修改未标记的 'O' 为 'X'，标记为 '#' 的恢复为 'O'。

示例输出

X X X X
X X X X
X X X X
X O X XO O O O
O X O X
O X O X
O O O O