问题遇到的现象和发生背景
有一个nm格的迷宫(表示有n行、m列),其中有可走的也有不可走的,如果用1表示可以走,0表示不可以走,文件读入这nm个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的,分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路,要求所走的路中没有重复的点,走时只能是上下左右四个方向。如果一条路都不可行,则输出相应信息(用-l表示无路)。
请统一用 左上右下的顺序拓展,也就是 (0,-1),(-1,0),(0,1),(1,0)
输入
第一行是两个数n,m( 1 < n , m < 15 ),接下来是m行n列由1和0组成的数据,最后两行是起始点和结束点。
输出
所有可行的路径,描述一个点时用(x,y)的形式,除开始点外,其他的都要用“->”表示方向。
如果没有一条可行的路则输出-1。
问题相关代码,请勿粘贴截图
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;
struct site{
int x,y;
site *next;
};
int n,m,num,flag;
site s,e;
site *t,*temp; //temp是一个中间指针,t拿来创建链表
site *be=&s; //be是起点指针,en是终点指针
site *en=&e;
int dx[]={0,-1,0,1},dy[]={-1,0,1,0};
void dfs(vector<vector<int> > a,int hashtable[][15]){
if(t->x==en->x&&t->y==en->y){
flag=0;
temp=be; //当t指向终点时,让temp变成be,开始输出
while(temp->x!=en->x&&temp->y!=en->y){
printf("(%d,%d)->",temp->x,temp->y);
temp=temp->next;
}
printf("(%d,%d)\n",temp->x,temp->y);
return;
}
for(int i=0;i<4;++i){
if(t->x+dx[i]>0&&t->x+dx[i]<=n&&t->y+dy[i]>0&&t->y+dy[i]<=m&&hashtable[t->x+dx[i]-1][t->y+dy[i]-1]==0&&a[t->x+dx[i]-1][t->y+dy[i]-1]==1){
site *t1=t;
temp->x=t->x+dx[i];temp->y=t->y+dy[i]; //t1储存t,方便还原
hashtable[temp->x-1][temp->y-1]=1;
t=t->next=temp; //t指向下一结点
dfs(a,hashtable);
hashtable[temp->x-1][temp->y-1]=0; //回溯
t=t1;
}
}
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
vector<vector<int> > a;
int hashtable[15][15]={0};
vector<int> son;
int tmp;
num=0;
flag=1;
for(int i=0;i<n;++i){
son.clear();
for(int j=0;j<m;++j){
scanf("%d",&tmp);
son.push_back(tmp);
}
a.push_back(son); //创建哈希表和迷宫
}
scanf("%d%d%d%d",&s.x,&s.y,&e.x,&e.y);
hashtable[s.x-1][s.y-1]=1;
t=be; //t先指向起点,起点标记为1
dfs(a,hashtable);
if(flag) printf("-1\n");
}
return 0;
}
运行结果及报错内容
不知道为什么没有输出,把指针换成结构体数组就没问题了
我的解答思路和尝试过的方法
我想要达到的结果
样例输入 Copy
5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6
样例输出 Copy
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)