走迷宫——深度优先搜索

Dear 丶 2022-06-17 06:46 160阅读 0赞

Think:  
1error ld returned 1 exit status错误可能原因：  
1>函数调用与定义名称不匹配或定义名称与预定义名称不匹配  
2>电脑多进程任务已进行（打开电脑任务管理器，将正在调试运行的程序关掉）

走迷宫  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
有一个m\*n格的迷宫（表示有m行、n列），其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，输入这m\*n个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用-1表示无路）。

Input  
第一行是两个数m，n（1< m, n< 15)，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。

Output  
所有可行的路径，输出时按照左上右下的顺序。描述一个点时用（x，y）的形式，除开始点外，其他的都要用“->”表示。如果没有一条可行的路则输出-1。

Example Input  
5 4  
1 1 0 0  
1 1 1 1  
0 1 1 0  
1 1 0 1  
1 1 1 1  
1 1  
5 4

Example Output  
(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)  
(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)  
(1,1)->(1,2)->(2,2)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)  
(1,1)->(1,2)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)  
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)  
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)  
(1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)  
(1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)

Hint

Author

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    struct node
    {
        int u;
        int v;
    }link[240];
    
    int tp, n, m, star_x, star_y, end_x, end_y, cnt;
    int flag[24][24], e[24][24];//flag数组标记当前结点是否被访问过，e数组记录当前结点是否可以通过
    int f[4][2] = {
       {
       0,-1}, {-1,0}, {
       0,1}, {
       1,0}};///位置移动
    
    int Judge_xy(int x, int y);//判断当前结点是否合法
    void Put_link();//输出路径
    void DFS(int x, int y);//深度优先搜索
    
    int main()
    {
        while(scanf("%d %d", &n, &m) != EOF)
        {
            tp = 0, cnt = 0;
            memset(flag, 0, sizeof(flag));//标记数组初始化
            memset(e, 0, sizeof(e));//地图数组初始化
    
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= m; j++)
                    scanf("%d", &e[i][j]);
    
            scanf("%d %d", &star_x, &star_y);
            scanf("%d %d", &end_x, &end_y);
    
            link[tp].u = star_x;//初始位置x坐标入队
            link[tp].v = star_y;//初始位置y坐标入队
            tp++;//已入队
            flag[star_x][star_y] = 1;//标记当前结点已通过
            DFS(star_x, star_y);//深度优先搜索
            if(cnt == 0)//如果无可行路径输出-1
                printf("-1\n");
        }
        return 0;
    }
    int Judge_xy(int x, int y)//判断当前结点是否合法
    {
        if(x < 1 || x > n || y < 1 || y > m)
            return 0;
        else
            return 1;
    }
    void Put_link()//输出路径
    {
        for(int i = 0; i < tp; i++)
            printf(i == 0? "(%d,%d)": "->(%d,%d)", link[i].u, link[i].v);
        printf("\n");
    }
    void DFS(int x, int y)//深度优先搜索
    {
        if(x == end_x && y == end_y)
        {
            cnt = 1;//标记存在可到达路径
            Put_link();//输出路径
            return;
        }
        else
        {
            for(int i = 0; i < 4;i++)
            {
                int xx = x + f[i][0];
                int yy = y + f[i][1];
                if(Judge_xy(xx, yy) && !flag[xx][yy] && e[xx][yy])
                {
                    link[tp].u = xx;//当前结点的x坐标入队
                    link[tp].v = yy;//当前结点的y坐标入队
                    tp++;//当前结点已入队
                    flag[xx][yy] = 1;//标记当前结点已经通过
                    DFS(xx, yy);//继续进行深度优先搜索
                    flag[xx][yy] = 0;//当前结点恢复进而判断其他可能
                    tp--;//当前结点出队进而判断其他可能
                }
            }
        }
    }
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 216KB
    Submit time: 2017-04-19 17:12:48
    ****************************************************/