使用d语言实现迷宫求解问题
时间: 2023-11-11 17:13:25 浏览: 75
以下是使用D语言实现迷宫求解问题的一个简单例子,采用深度优先搜索(DFS)算法:
```d
import std.stdio;
import std.algorithm;
import std.array;
const char WALL = '#';
const char ROAD = '.';
const char START = 'S';
const char END = 'E';
const int[][] DIRS = [[-1, 0], [0, -1], [1, 0], [0, 1]]; // 上左下右四个方向
void dfs(int[][] maze, int x, int y, int[][] visited) {
visited[x][y] = 1; // 标记为已访问
if (maze[x][y] == END) { // 到达终点,输出路径并返回
writeln("Solution found:");
foreach (row; maze) {
writeln(row.joiner(""));
}
return;
}
foreach (dir; DIRS) {
int nx = x + dir[0], ny = y + dir[1];
if (nx < 0 || ny < 0 || nx >= maze.length || ny >= maze[0].length) {
continue; // 超出边界,跳过
}
if (maze[nx][ny] == WALL || visited[nx][ny] != 0) {
continue; // 障碍物或已访问,跳过
}
maze[nx][ny] = ROAD; // 标记为走过
dfs(maze, nx, ny, visited); // 递归搜索
maze[nx][ny] = ' '; // 还原为未走过
}
}
void main() {
int[][] maze = [
[WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL],
[WALL, START, ROAD, ROAD, WALL, ROAD, ROAD, WALL],
[WALL, ROAD, WALL, ROAD, WALL, ROAD, WALL, WALL],
[WALL, ROAD, ROAD, ROAD, ROAD, ROAD, ROAD, WALL],
[WALL, ROAD, WALL, ROAD, WALL, ROAD, WALL, WALL],
[WALL, ROAD, ROAD, ROAD, ROAD, ROAD, ROAD, WALL],
[WALL, WALL, WALL, WALL, WALL, WALL, END, WALL],
];
int[][] visited = new int[maze.length][maze[0].length]; // 记录已访问的位置
dfs(maze, 1, 1, visited); // 从起点开始搜索
}
```
该程序定义了一个迷宫二维数组和一个visited数组,用于记录已访问的位置。程序从起点开始进行DFS搜索,对于每个可以走的方向,都尝试递归搜索下一步,直到到达终点或所有方向都走过为止。如果找到了解决方案,就输出路径并返回。注意在递归搜索过程中需要用一个visited数组记录已访问的位置,防止重复访问。
阅读全文