深度优先搜索算法：计算可达黑色方砖数量

在这个问题中，我们需要解决的是在一个由红色(R)和黑色(B)方砖组成的矩形房间里，从一个特定的起始点@开始，利用深度优先搜索(DFS)算法找出可以到达的所有黑色方砖的数量。房间的布局遵循一定的规则：人在红砖上无法移动，而在黑砖上可以向上下左右四个方向移动。任务是编写一个程序，使用Python、C语言和Java三种不同的编程语言实现这一功能。 Python实现： ```python def count_black_tiles(room): rows, cols = len(room), len(room[0]) def dfs(row, col): if not (0 <= row < rows and 0 <= col < cols and room[row][col] == 'B'): return 0 room[row][col] = '#' # 标记已访问 count = 1 + dfs(row - 1, col) + dfs(row + 1, col) + dfs(row, col - 1) + dfs(row, col + 1) # 四方向搜索 return count start_row, start_col = None, None for i in range(rows): for j in range(cols): if room[i][j] == '@': start_row, start_col = i, j break if start_row is not None and start_col is not None: black_count = dfs(start_row, start_col) return black_count # 示例 room = [ ['@', 'R', 'B', 'B', 'R'], ['R', 'B', 'R', 'R', 'B'], ['B', 'R', 'B', 'R', 'R'], ['B', 'B', 'R', 'B', 'R'], ['R', 'B', 'R', 'R', 'B'] ] result = count_black_tiles(room) print("可以到达的黑色方砖数量：", result) ``` C语言实现： ```c #include <stdio.h> #include <stdlib.h> typedef struct { int row, col; } Coord; char board[5][5]; // 假设房间大小为5x5 int visited[5][5] = {0}; // 记录已访问方砖 int count = 0; void dfs(Coord start) { visited[start.row][start.col] = 1; if (board[start.row][start.col] == 'B') { count++; } for (int i = -1; i <= 1; i++) { for (int j = -1; j <= 1; j++) { int newRow = start.row + i; int newCol = start.col + j; if (newRow >= 0 && newRow < 5 && newCol >= 0 && newCol < 5 && !visited[newRow][newCol] && board[newRow][newCol] == 'B') { dfs((Coord){newRow, newCol}); } } } } int main() { char* room[] = {"@@@@RBRBR", "RBBRBRB", "BRRBRBR", "BBBRBRB", "RBRBRBB"}; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { board[i][j] = room[i][j]; } } Coord start = {0, 0}; if (board[start.row][start.col] == '@') { dfs(start); printf("可以到达的黑色方砖数量：%d\n", count); } return 0; } ``` Java实现： ```java import java.util.*; public class Main { private static final char BLACK = 'B'; private static final char EMPTY = '.'; private static final char START = '@'; public static void main(String[] args) { char[][] room = { {'@', 'R', 'B', 'B', 'R'}, {'R', 'B', 'R', 'R', 'B'}, {'B', 'R', 'B', 'R', 'R'}, {'B', 'B', 'R', 'B', 'R'}, {'R', 'B', 'R', 'R', 'B'} }; int blackCount = countBlackTiles(room); System.out.println("可以到达的黑色方砖数量：" + blackCount); } private static int countBlackTiles(char[][] room) { int rows = room.length, cols = room[0].length; boolean[][] visited = new boolean[rows][cols]; int dfs(int row, int col) { if (row < 0 || row >= rows || col < 0 || col >= cols || room[row][col] != BLACK || visited[row][col]) { return 0; } visited[row][col] = true; int count = 1; count += dfs(row - 1, col); count += dfs(row + 1, col); count += dfs(row, col - 1); count += dfs(row, col + 1); return count; } for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (room[i][j] == START) { return dfs(i, j); } } } return 0; } } ``` 以上三种编程语言的代码都采用了深度优先搜索策略，通过递归的方式遍历房间中的每一个方砖，遇到黑色方砖时计数并继续探索其相邻的黑色方砖，直到遍历完整个房间。在Python和Java版本中，我们还使用了数组来标记已访问的方砖，防止重复搜索。在C语言中，我们用一个二维数组`visited`来达到同样的效果。