• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

c++走迷宫

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

题目描述

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

*/

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#获取汉字的全拼发布时间:2022-07-13
下一篇:
基于TestStand和C#开发平台TTStand初识系列之三【Development】发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap