给定一个nn的包含‘X’和‘O’的面板,捕捉所有被‘X’环绕的区域,并将该区域中的所有‘O’翻转为‘X’。C语言
时间: 2023-09-27 16:11:31 浏览: 57
实现思路如下:
1. 先遍历四周的边界,将被‘O’包围的区域标记出来,用另一个字符或数字来标识。
2. 对于面板内部(不在四周边界上),若该位置是‘O’且未被标记为被‘X’包围,则认为该位置与边界有联通,不会被‘X’包围,将其标记为另一个字符或数字。
3. 遍历整个面板,将所有被标记为被‘X’包围的区域内的‘O’替换为‘X’。
下面是实现代码:
```c
void solve(char** board, int boardSize, int* boardColSize){
if(board == NULL || boardSize == 0 || boardColSize == NULL) {
return;
}
int i, j;
int row = boardSize, col = boardColSize[0];
// Step 1: traverse the four boundaries, mark the enclosed area
for(i = 0; i < row; i++) {
if(board[i][0] == 'O') dfs(board, i, 0, row, col, '#'); // left boundary
if(board[i][col-1] == 'O') dfs(board, i, col-1, row, col, '#'); // right boundary
}
for(j = 0; j < col; j++) {
if(board[0][j] == 'O') dfs(board, 0, j, row, col, '#'); // top boundary
if(board[row-1][j] == 'O') dfs(board, row-1, j, row, col, '#'); // bottom boundary
}
// Step 2: traverse the internal area, mark the unenclosed area
for(i = 1; i < row-1; i++) {
for(j = 1; j < col-1; j++) {
if(board[i][j] == 'O' && board[i][j] != '#') {
dfs(board, i, j, row, col, 'X'); // unenclosed area
}
}
}
// Step 3: replace all 'O' in enclosed area to 'X'
for(i = 0; i < row; i++) {
for(j = 0; j < col; j++) {
if(board[i][j] == 'O') board[i][j] = 'X';
if(board[i][j] == '#') board[i][j] = 'O';
}
}
}
void dfs(char **board, int i, int j, int row, int col, char mark) {
if(i < 0 || i >= row || j < 0 || j >= col || board[i][j] == '#' || board[i][j] == mark) {
return;
}
board[i][j] = mark; // mark the current position
dfs(board, i+1, j, row, col, mark); // move down
dfs(board, i-1, j, row, col, mark); // move up
dfs(board, i, j+1, row, col, mark); // move right
dfs(board, i, j-1, row, col, mark); // move left
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)