7-10 sdut-C语言实验-走迷宫
分数 20
全屏浏览
切换布局
作者 马新娟
单位 山东理工大学
有一个mn格的迷宫（表示有m行、n列），其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，输入这mn个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用-1表示无路）。
输入格式:
第一行是两个数m，n（1< m, n< 15)，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。
输出格式:
所有可行的路径，输出时按照左上右下的顺序。描述一个点时用（x，y）的形式，除开始点外，其他的都要用“->”表示。如果没有一条可行的路则输出-1。
输入样例:
在这里给出一组输入。例如：
1. 5 4 2. 1 1 0 0 3. 1 1 1 1 4. 0 1 1 0 5. 1 1 0 1 6. 1 1 1 1 7. 1 1 8. 5 4
输出样例:
在这里给出相应的输出。例如：
(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)
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
# include<stdio.h> # include<string.h> int a[30][30]; int b[100]; //用于储存路径输出 int dir[4][2]={{0,-1},{-1,0},{0,1},{1,0}}; //4个方向 int c,d,flag; void work(int g,int h,int ii); int main( ) //1269--走迷宫 { int n,m,g,h,i,j,ii; while(scanf("%d %d",&n,&m) == 2) { ii = flag = 0; memset(b,0,sizeof(b)); memset(a,0,sizeof(a)); for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&a[i][j]); scanf("%d %d %d %d",&g,&h,&c,&d); work(g,h,0); if(!flag) printf("-1\n"); } return 0; } void work(int g,int h,int ii) { int i; if(g == c && h == d ) //来到终点则输出 { flag = 1; for(i=0;i<ii;i+=2) { printf("(%d,%d)",b[i],b[i+1]); if(i<ii) printf("->"); } printf("(%d,%d)\n",c,d); return; } if(!a[g][h])return ; //到达边界或已走或墙壁返回 for(i=0;i<4;i++) //依次走4个方向 { a[g][h] = 0; //如果该方向可走，则标记已走，为0 b[ii] = g; //记下坐标 b[ii+1] = h; work(g+dir[i][0],h+dir[i][1],ii+2); //走下一步 a[g][h] = 1; //恢复 } }
