weixin_57870673 2021-12-12 17:22 采纳率: 0%
浏览 16
已结题

走迷宫,dfs使用指针链表输出不了

问题遇到的现象和发生背景

 有一个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)

  • 写回答

1条回答 默认 最新

  • 有问必答小助手 2021-12-13 18:36
    关注

    你好,我是有问必答小助手,非常抱歉,本次您提出的有问必答问题,技术专家团超时未为您做出解答


    本次提问扣除的有问必答次数,将会以问答VIP体验卡(1次有问必答机会、商城购买实体图书享受95折优惠)的形式为您补发到账户。


    因为有问必答VIP体验卡有效期仅有1天,您在需要使用的时候【私信】联系我,我会为您补发。

    评论

报告相同问题?

问题事件

  • 系统已结题 12月20日
  • 创建了问题 12月12日

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 MATLAB动图问题
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名