c++ 走迷宫
发布时间:2020-12-16 10:40:27 所属栏目:百科 来源:网络整理
导读:题目描述 有一个n m格的迷宫(表示有n行、m列),其中有可走的也有不可走的,如果用1表示可以走,0表示不可以走,文件读入这n m个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的,分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路,
题目描述有一个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,2)->(2,3)->(2,4)->(2,5)->(3,4)->(3,3)->(4,4)->(4,5)->(5,6) (1,5)->(4,3)->(3,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,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,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 %dnn",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,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,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 */ (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |