用dfs算法写一个迷宫代码
时间: 2023-11-17 07:11:08 浏览: 33
好的,我可以为您提供一个简单的迷宫代码,基于深度优先搜索算法(DFS)。
假设迷宫是一个二维数组,其中0表示可通行的空白格子,1表示障碍格子,迷宫的入口是起点坐标(startX,startY),出口是终点坐标(targetX,targetY)。
以下是代码实现:
```
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100;
int n, m; //迷宫的行数和列数
int maze[MAXN][MAXN]; //迷宫地图
bool visited[MAXN][MAXN]; //标记是否走过
//DFS搜索函数
bool dfs(int x, int y) {
//判断是否到达终点
if (x == targetX && y == targetY)
return true;
visited[x][y] = true; //标记为已走过
bool flag = false;
//上
if (x > 0 && maze[x-1][y] == 0 && !visited[x-1][y])
flag |= dfs(x-1, y);
//下
if (x < n-1 && maze[x+1][y] == 0 && !visited[x+1][y])
flag |= dfs(x+1, y);
//左
if (y > 0 && maze[x][y-1] == 0 && !visited[x][y-1])
flag |= dfs(x, y-1);
//右
if (y < m-1 && maze[x][y+1] == 0 && !visited[x][y+1])
flag |= dfs(x, y+1);
return flag;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> maze[i][j];
int startX, startY, targetX, targetY;
cin >> startX >> startY >> targetX >> targetY;
bool ans = dfs(startX, startY);
if (ans)
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
```
注:这里使用了位运算中的或运算符(|),表示只要有一个dfs返回true,就返回true。