社区讨论
哪里有问题请帮我找一下,找了一上午,最后直接折了
P1238走迷宫参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mhjhl86e
- 此快照首次捕获于
- 2025/11/04 02:41 4 个月前
- 此快照最后确认于
- 2025/11/04 02:41 4 个月前
CPP
//搜索dfs 走迷宫
#include <iostream>
#include <cstdio>
using namespace std;
int m,n;//有 m 行、n 列
short a[20][20]; //迷宫
bool b[20][20] = {0},found = false;
int ans[1000][2];
short x[4] = {-1,0,1,0},y[4] = {0,1,0,-1}; //左上右下 优先顺序
short start_x,start_y,end_x,end_y; //最后两行是起始点和结束点
void print(int len);
void search(int p,int q,int k); //初始坐标(p,q),当前路径长度k
int main()
{
cin >> m >> n;
for (int i=0;i<m;i++)
for (int j=0;j<n;j++)
cin >> a[i][j];
cin >> start_x >> start_y >> end_x >> end_y;
b[start_x][start_y] = 1;
search(start_x,start_y,0); //起点等着直接输出'
if (found == false)
{
cout << -1 ;
return 0;
}
return 0;
}
void search(int p,int q,int k)
{
for (int i=0;i<4;i++)
{
int xx = p + x[i];
int yy = q + y[i];
if (!b[xx][yy] && xx >=0 && xx<m && yy>=0 && yy<n && a[xx][yy] == 1) //可以走,不越界,没走过
{
b[xx][yy] = 1;
ans[k][0] = xx; //没办法,先不存储起点了,但是,按照这里的写法,终点应该 会 被 存
ans[k][1] = yy;
if (xx == end_x && yy == end_y)
{
print(k);
found = true;
}
else search(xx,yy,k+1);
b[xx][yy] = 0; //回溯 backtracking
}
}
}
void print(int len)
{
cout << "(" << start_x <<"," << start_y << ")" ; //每一次,都先输出起点
for (int i=0;i<=len;i++)
{
printf("->(%d,%d)",ans[i][0],ans[i][1]);
}
cout << endl;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...