首页 > 代码库 > HDU 2102 A计划 DFS与BFS两种写法
HDU 2102 A计划 DFS与BFS两种写法
1.题意：一位公主被困在迷宫里，一位勇士前去营救，迷宫为两层，规模为N*M，迷宫入口为(0,0,0),公主的位置用‘P‘标记；迷宫内，‘.‘表示空地，‘*‘表示墙，特殊的，‘#‘表示时空传输机，走到这里就会被传输到另一层的相对位置；在迷宫内没走动一步耗时为1，最终求解是否能在T时刻解救到公主；
2.输入输出：第一行C表示C组数据，每一组内N,M,T给出的迷宫规模与时间，接着给出了双层迷宫的内容；若是能找到公主输出"YES",否则"NO"；
3.分析：这里原题意判断是否能在T时刻找到，然而要是写搜索判断有没有"时刻为T且位置为P"的状态，会超时，所以直接判断能不能在T时刻之前就找到；
BFS版：求出到达P处的最短时间并判断是否小于T；DFS版：找到第一个"时刻小于T且位置为P的状态"就返回；
1 # include <iostream>
2 # include <cstdio>
3 # include <queue>
4 # include <cstring>
5 using namespace std;
6 const int maxn=15;
7 int N,M,T;
8 int dx[4]={0,0,-1,1};
9 int dy[4]={-1,1,0,0};
10 char maze[2][maxn][maxn];
11 int vis[2][maxn][maxn];
12 struct Node
13 {
14 int l,x,y,t;
15 Node(){}
16 Node(int ll,int xx,int yy,int tt)
17 {
18 l=ll;
19 x=xx;
20 y=yy;
21 t=tt;
22 }
23 };
24 void Init()
25 {
26 scanf("%d%d%d",&N,&M,&T);
27 for(int i=0;i<2;i++)
28 for(int j=0;j<N;j++)
29 scanf("%s",maze[i][j]);
30 memset(vis,0,sizeof(vis));
31 }
32 void Solve()
33 {
34 int ans=-1;
35 queue<Node> Q;
36 vis[0][0][0]=1;
37 Q.push(Node(0,0,0,0));
38 while(!Q.empty())
39 {
40 Node temp=Q.front();
41 Q.pop();
42 if(temp.t<=T&&maze[temp.l][temp.x][temp.y]==‘P‘)
43 {
44 ans=1;
45 break;
46 }
47 if(temp.t>T) break;
48 for(int i=0;i<4;i++)
49 {
50 int nx=temp.x+dx[i];
51 int ny=temp.y+dy[i];
52 if(nx>=0&&ny>=0&&nx<N&&ny<M&&maze[temp.l][nx][ny]!=‘*‘&&!vis[temp.l][nx][ny])
53 {
54 if(maze[temp.l][nx][ny]!=‘#‘)//"."
55 {
56 vis[temp.l][nx][ny]=1;
57 Q.push(Node(temp.l,nx,ny,temp.t+1));
58 }
59 else//‘#‘
60 {
61 vis[temp.l][nx][ny]=vis[!temp.l][nx][ny]=1;
62 if(maze[!temp.l][nx][ny]!=‘*‘&&maze[!temp.l][nx][ny]!=‘#‘)
63 Q.push(Node(!temp.l,nx,ny,temp.t+1));
64 }
65 }
66 }
67 }
68 if(ans>0) printf("YES\n");
69 else printf("NO\n");
70 }
71 int main()
72 {
73 //freopen("in.txt","r",stdin);
74 //freopen("out.txt","w",stdout);
75 int C;
76 scanf("%d",&C);
77 while(C--)
78 {
79 Init();
80 Solve();
81 }
82 return 0;
83 }
1 # include <iostream>
2 # include <cstdio>
3 # include <cstring>
4 # include <cstdlib>
5 using namespace std;
6 const int MAXN=15;
7 char Maze[2][MAXN][MAXN];
8 int dx[4]={1,-1,0,0};
9 int dy[4]={0,0,1,-1};
10 int vis[2][MAXN][MAXN];
11 int N,M,T,f;
12 void Init()
13 {
14 f=0;
15 scanf("%d%d%d",&N,&M,&T);
16 for(int k=0;k<2;k++)
17 for(int i=0;i<N;i++)
18 scanf("%s",Maze[k][i]);
19 memset(vis,0,sizeof(vis));
20 }
21 void dfs(int k,int x,int y,int t)
22 {
23 if(f) return;
24 if(t<T&&Maze[k][x][y]==‘P‘)
25 {
26 f=1;
27 return;
28 }
29 if(t==T)
30 {
31 if(Maze[k][x][y]==‘P‘)
32 f=1;
33 return;
34 }
35 for(int i=0;i<4;i++)
36 {
37 int nx=x+dx[i];
38 int ny=y+dy[i];
39 if(nx>=0&&ny>=0&&nx<N&&ny<M&&Maze[k][nx][ny]!=‘*‘)
40 {
41 if(Maze[k][nx][ny]!=‘#‘&&!vis[k][nx][ny])
42 {
43 vis[k][nx][ny]=1;
44 dfs(k,nx,ny,t+1);
45 vis[k][nx][ny]=0;
46 }
47 else
48 {
49 if(Maze[!k][nx][ny]!=‘#‘&&Maze[!k][nx][ny]!=‘*‘)
50 if(!vis[k][nx][ny]&&!vis[!k][nx][ny])
51 {
52 vis[!k][nx][ny]=vis[k][nx][ny]=1;
53 dfs(!k,nx,ny,t+1);
54 vis[!k][nx][ny]=vis[k][nx][ny]=0;
55 }
56 }
57 }
58 }
59 }
60 void Solve()
61 {
62 dfs(0,0,0,0);
63 if(f) printf("YES\n");
64 else printf("NO\n");
65 }
66 int main()
67 {
68 //freopen("in.txt","r",stdin);
69 //freopen("out.txt","w",stdout);
70 int C;
71 scanf("%d",&C);
72 while(C--)
73 {
74 Init();
75 Solve();
76 }
77 return 0;
78 }
HDU 2102 A计划 DFS与BFS两种写法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。