用C语言代码完成这个问题: 给定一个包含‘X’和‘O'的面板,捕捉所有被‘X’环绕的区域,并将该区域城中的所有‘O'翻转为'X'。例如面板如下: X X X X X 0 0 X X X 0 X X 0 X X 在执行程序后变为: X X X X X X X X X X X X X O X X 要求采用DFS和BFS两种方法求解。
时间: 2024-02-10 14:08:42 浏览: 72
DFS方法的C语言代码如下:
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 100
int row, col;
char board[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];
void dfs(int x, int y) {
if (x < 0 || x >= row || y < 0 || y >= col || board[x][y] == 'X' || visited[x][y]) {
return;
}
visited[x][y] = true;
dfs(x - 1, y);
dfs(x + 1, y);
dfs(x, y - 1);
dfs(x, y + 1);
}
void solve(void) {
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if ((i == 0 || i == row - 1 || j == 0 || j == col - 1) && board[i][j] == 'O' && !visited[i][j]) {
dfs(i, j);
}
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'O' && !visited[i][j]) {
board[i][j] = 'X';
}
}
}
}
int main() {
scanf("%d%d", &row, &col);
for (int i = 0; i < row; i++) {
scanf("%s", board[i]);
}
solve();
for (int i = 0; i < row; i++) {
printf("%s\n", board[i]);
}
return 0;
}
```
BFS方法的C语言代码如下:
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
int x;
int y;
} Point;
int row, col;
char board[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];
void bfs(Point* queue, int front, int rear) {
const int dx[4] = { -1, 1, 0, 0 };
const int dy[4] = { 0, 0, -1, 1 };
while (front <= rear) {
Point p = queue[front++];
for (int i = 0; i < 4; i++) {
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if (nx >= 0 && nx < row && ny >= 0 && ny < col && board[nx][ny] == 'O' && !visited[nx][ny]) {
visited[nx][ny] = true;
queue[++rear] = (Point) { nx, ny };
}
}
}
}
void solve(void) {
Point queue[MAX_SIZE * MAX_SIZE];
int front = 0, rear = -1;
for (int i = 0; i < row; i++) {
if (board[i][0] == 'O' && !visited[i][0]) {
visited[i][0] = true;
queue[++rear] = (Point) { i, 0 };
}
if (board[i][col - 1] == 'O' && !visited[i][col - 1]) {
visited[i][col - 1] = true;
queue[++rear] = (Point) { i, col - 1 };
}
}
for (int j = 0; j < col; j++) {
if (board[0][j] == 'O' && !visited[0][j]) {
visited[0][j] = true;
queue[++rear] = (Point) { 0, j };
}
if (board[row - 1][j] == 'O' && !visited[row - 1][j]) {
visited[row - 1][j] = true;
queue[++rear] = (Point) { row - 1, j };
}
}
bfs(queue, front, rear);
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'O' && !visited[i][j]) {
board[i][j] = 'X';
}
}
}
}
int main() {
scanf("%d%d", &row, &col);
for (int i = 0; i < row; i++) {
scanf("%s", board[i]);
}
solve();
for (int i = 0; i < row; i++) {
printf("%s\n", board[i]);
}
return 0;
}
```
阅读全文