首页 > 代码库 > Maze Exploration UVA 784 (简单的深度优先搜索)
Maze Exploration UVA 784 (简单的深度优先搜索)
说说:
这道题的题意,事先题目给你如下图所示:
XXXXXXXXX
X X X
X * X
X X X
XXXXXXXXX
X X
X X
X X
XXXXX
可以把以上图像想象成一间房子,字符‘X‘是围墙,你现在所处的位置是‘*‘所在的地方,要求你将’*‘周围的空白,包括‘*‘本身全部用‘#代替。注意不能穿越围墙。其实就是最最基础的深度遍历的问题,只要找到‘*‘所在的位置,然后查看周围是否为空格,是则填上‘#‘,然后递归,否则函数直接返回即可。
源代码:
#include <stdio.h> #include <string.h> #define MAXW 80+5 #define MAXH 30+5 char room[MAXH][MAXW]; void dfs(int,int); int main(){ int T,n,x,y,i; freopen("data","r",stdin); // scanf("%d",&T); getchar(); while(T--){ n=0; while(gets(room[n])) if(room[n][0]=='_') break; else n++; for(x=0;x<n;x++)//找到初始位置 for(y=0;y<strlen(room[x]);y++) if(room[x][y]=='*') dfs(x,y); for(x=0;x<=n;x++) printf("%s\n",room[x]); } return 0; } void dfs(int x,int y){ if(room[x][y]==' '||room[x][y]=='*') room[x][y]='#'; else return; //对当前点的四周进行遍历 dfs(x-1,y-1);dfs(x,y-1);dfs(x+1,y-1); dfs(x-1,y); dfs(x+1,y); dfs(x-1,y+1);dfs(x,y+1);dfs(x+1,y+1); return ; }
Maze Exploration UVA 784 (简单的深度优先搜索)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。