首页 > 代码库 > UVa 784 迷宫探索

UVa 784 迷宫探索

题意:迷宫里有X作为墙,空格为可通过,*标记起点。然后需要你现在来刷墙,刷那些由起点可达的房间的墙,即找由起点可达的连通块。这里题目说墙是除几个字符之外的可打印字符,没有说是X。做题时当成了X,结果AC了~题目说到墙都是3格子宽1格子厚,好像也没什么用~

思路:输入时找到起点并记下,然后由起点深搜。

注意:从网站拷贝样例数据到txt时,它自动地少了很多空格,导致这个测试数据时不符合题意的。(不容易发现复制粘贴过程中少了很多空格~)这样的话,如果是我代码中dfx中的注释掉的那个 if 语句,程序就会崩溃。(原因是我之前初始化时用的是空字符初始化maze,然后被修改了的测试数据里导致有的空格字符上方是空字符~)

这里用字符X来初始化maze,由于X作为墙封闭了整个maze,就不再需要像之前几题那样在maze外围一圈 X 来避免判断坐标是否出界。这里直接可不用判断坐标是否出界。

不难,但那个崩溃调了好久,没想到是拷贝样例数据出了问题~

Code:

//#define LOCAL
#include<stdio.h>
#include<string.h>
#define MAXH 35
#define MAXL 90

void dfs(int x,int y);

char maze[MAXH][MAXL];
//int visit[MAXH][MAXL];
int dir[][4]={{-1,1,0,0},{0,0,-1,1}};//LRUD

int main()
{
 #ifdef LOCAL
  freopen("784.in","r",stdin);
  freopen("784.out","w",stdout);
 #endif 
 int n;
 scanf("%d",&n);
 getchar();
 while(n-->0)
 {
  memset(maze,'X',sizeof(maze));
  char s[MAXL];
  int h=0;
  int sx=0,sy=0;
  while(gets(s) && s[0]!='_')//是下划线_不是短线- 
  {//printf("%s\n",s);
   int len=strlen(s);
   for(int i=0;i<=len;++i)//小于等于len,将最后的\0也赋到最后             
   { 
    maze[h][i]=s[i];
    if(maze[h][i]=='*') { sx=h; sy=i;}
   }
   h++;
  }
  strcpy(maze[h++],s); 
  dfs(sx,sy);
  for(int i=0;i<h;++i) 
   printf("%s\n",maze[i]);
 }
 return 0;   
}

void dfs(int x,int y)
{
 //if(maze[x][y]=='X'||maze[x][y]=='#'||maze[x][y]=='_') return ;
 if(maze[x][y]!=' ' && maze[x][y]!='*') return ;
 //visit[x][y]=1;
 maze[x][y]='#';
 for(int i=0;i<4;++i)
 {
  int nx=x+dir[1][i];//行应该是加dir[0]即加y 
  int ny=y+dir[0][i];
  dfs(nx,ny);       
 }    
} 


UVa 784 迷宫探索