首页 > 代码库 > wikioi 1215 迷宫
wikioi 1215 迷宫
1215 迷宫
6人推荐 收藏 发题解
题目描述 Description
在N*N的迷宫内，“#”为墙，“.”为路，“s”为起点，“e”为终点，一共4个方向可以走。从左上角（(0,0)“s”）位置处走到右下角（(n-1,n-1)“e”）位置处，可以走通则输出YES，不可以走则输出NO。
输入描述 Input Description
输入的第一行为一个整数m，表示迷宫的数量。 其后每个迷宫数据的第一行为一个整数n（n≤16），表示迷宫的边长，接下来的n行每行n个字符，字符之间没有空格分隔。
输出描述 Output Description
输出有m行，每行对应的迷宫能走，则输出YES，否则输出NO。
样例输入 Sample Input
1 7 s...##. .#..... ....... ..#.... ..#...# ###...# ......e样例输出 Sample Output
YES
这道题灌水法即可，简单说就是DFS然后向四周拓展
#include<stdio.h>#include<math.h>char a[1001][1001],ans=0;int directx[5]={0,0,0,-1,1},vis[1001][1001];int directy[5]={0,-1,1,0,0};void dfs(int i,int j,int n){ if(i<=0||i>n||j<=0||j>n)return ; if(vis[i][j]==1||a[i][j]==‘#‘)return ; if(a[i][j]==‘e‘){ans=a[i][j]; printf("YES"); } vis[i][j]=1; for(int x=1;x<=4;x++) dfs(i+directx[x],j+directy[x],n) ;}int main(){ int b,i,z,o,j,n; scanf("%d",&z); for(o=1;o<=z;o++) { scanf("%d\n",&n); for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(j<n) scanf("%c",&a[i][j]); else scanf("%c\n",&a[i][j]); } dfs(1,1,n); if(ans==0)printf("NO"); printf("\n"); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。