离散数学迷宫问题
从一个迷宫的入口到出口找出一条可通路经。用一个二维数组MG(0：M，0：N)模拟迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。MG(1，1)和MG(M-1，N-1)分别为迷宫50
输入
1.输入迷宫的大小M行和N列，两者为整数
2.给定MG[M，N]各元素的值（0或1），建立迷宫。
输出
是否有通路（YES或NO）
样例输入
55
111111
100001
100011
100101
100101
111111
样例输出
NO
提示
1）读入两个整数M，N后，迷宫的大小是0~M和0~N，也就是实际上有M+1行和N+1列
2）判断是否有通路主要是判断点（1，1）到点（M-1，N-1）之间是否有通路，第0行、第M行、第1列、第N列的所有值都一定是1。
#include"stdio.h"struct{inti;intj;intdi;}stack[10000];inttop=-1;intfun(){intmg[500][500],i,j,di,find,N,M,x,y;scanf("%d%d",&M,&N);for(x=0;x<=M;x++)for(y=0;y<=N;y++)scanf("%d",&mg[x][y]);top++;stack[top].i=1;stack[top].j=1;stack[top].di=-1;mg[1][1]=-1;while(top>=0){i=stack[top].i;j=stack[top].j;di=stack[top].di;if(i==M-1&&j==N-1){printf("YES\n");return0;}find=0;while(di<4&&find==0){di++;if(di==0){i=(stack[top].i)-1;j=stack[top].j;}if(di==1){i=stack[top].i;j=(stack[top].j)+1;}if(di==2){i=(stack[top].i)+1;j=stack[top].j;}if(di==3){i=stack[top].i;j=(stack[top].j)-1;}if(mg[i][j]==0){find=1;break;}}if(find==1){stack[top].di=di;top++;stack[top].i=i;stack[top].j=j;stack[top].di=-1;mg[i][j]=-1;}else{mg[stack[top].i][stack[top].j]=1;top--;}}printf("NO\n");return0;}intmain(){fun();return0;}
|
|
