题目描述

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

请统一用 左上右下的顺序拓展，也就是 (0,-1),(-1,0),(0,1),(1,0)

输入

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

输出

所有可行的路径，描述一个点时用(x，y)的形式，除开始点外，其他的都要用“->”表示方向。

如果没有一条可行的路则输出-1。

样例输入

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

样例输出

(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)

Source Code

#include <iostream>
#include <string.h>
#include <stdio.h>

int n,m,a[20][20],sx,sy,tx,ty,ans[300][2],used[20][20],opt[20][20],flag;
int d[4][2]={{0,-1},
             {-1,0},
             {0,1},
             {1,0}};
void dfs(int x,int y,int step)//step是步数
{
    if(x == tx && y == ty)//如果起点等于终点
    {
        memset(opt,0,sizeof(opt));//memset把opt[]清零
        for(int i = 1;i <= step;i ++)//循环输出步数
            if(opt[ans[i][0]][ans[i][1]] == 1) return ;//这是一条可行路线
            else opt[ans[i][0]][ans[i][1]] = 1;
        printf("(%d,%d)",ans[1][0],ans[1][1]);
        for(int i = 2;i <= step;i ++)//循环输出除了起点的所有路线
            printf("->(%d,%d)",ans[i][0],ans[i][1]);//ans[2][0]输出第2步的x坐标ans[2][1]输出第2步的y坐标
        printf("\n");
        flag = 1;//flag = 1表示已经输出过(有可行的路线)
        return ;
    }
    for(int i=0;i<4;i++)
    {
        int vx = x + d[i][0],vy = y + d[i][1];//上下左右扩展
        if(vx < 1 || vx > n || vy < 1 || vy > m) continue;//如果在迷宫外面
        if(a[vx][vy] == 0) continue;//如果不能走
        if(used[vx][vy] == 1) continue;//如果走过
        used[vx][vy] = 1;//标位已经走过 作用:不能重复走
//        printf("%d   %d   %d\n\n",vx,vy,step + 1);
        ans[step + 1][0] = vx;ans[step + 1][1] = vy;//ans[2][0]输出第2步的x坐标ans[2][1]输出第2步的y坐标
        dfs(vx,vy,step + 1);//递归寻找下一个可以走的节点(不断递归下一个节点是否可行,如果下个节点B的其中两个方向被堵死,第三个方向C虽然能走,但是C被堵死 也删除下个节点B)

        used[vx][vy] = 0;
    }
}
int main()
{
    std::cin >> n >> m;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            std::cin >> a[i][j];//矩阵转换成数组
    std::cin >> sx >> sy;//起点
    std::cin >> tx >> ty;//终点
    ans[1][0] = sx;//ans[1][0]:1表示步数  0表示存的是x坐标
    ans[1][1] = sy;//ans[1][0]:1表示步数  1表示存的是y坐标
    dfs(sx,sy,1);//从起点开始递归查找
    if(flag == 0)
        printf("-1");
    return 0;
}
/*
 input:

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

*/