HDU2102 A计划（bfs）

A计划

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 30050 Accepted Submission(s): 7533

Problem Description

可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。
现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S（0，0，0），公主的位置用P表示，时空传输机用#表示，墙用*表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。

Input

输入的第一行C表示共有C个测试数据，每个测试数据的前一行有三个整数N，M，T。 N，M迷宫的大小N*M（1 <= N,M <=10)。T如上所意。接下去的前N*M表示迷宫的第一层的布置情况，后N*M表示迷宫第二层的布置情况。

Output

如果骑士们能够在T时刻能找到公主就输出“YES”，否则输出“NO”。

Sample Input

5 5 14

S*#*.

.#...

.....

****.

...#.

..*.P

#.*..

***..

...*.

*.#..

Sample Output

YES

广度优先搜索。

骑士救出公主的最小时间小于等于T即可。

找了一处很久的bug，一开始将isvisit数组设为bool类型，用memset函数初始化为0时发生了某种我暂且未知的错误（感谢什造提醒），后将bool类型改为int类型后AC。

AC代码：

 1 #include<iostream>
 2 #include<sstream>
 3 #include<algorithm>
 4 #include<string>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<vector>
 8 #include<cmath>
 9 #include<ctime>
10 #include<stack>
11 #include<queue>
12 using namespace std;
13 char maze[2][10][10];
14 int isvisit[2][10][10];
15 int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};//方向数组 
16 int N,M; 
17 struct node
18 {
19     int order,x,y,time;//地图的种类，行，列，时间 
20     node(int a,int b,int c,int d)
21     {
22         order=a;x=b;y=c;time=d;
23     }
24 };
25 bool bfs(int T)
26 {
27     queue<node> que;
28     memset(isvisit,0,sizeof(isvisit));
29     que.push(node(0,0,0,0));//起点是(0,0,0),起始时间是0 
30     isvisit[0][0][0]=1;//标记状态 
31     while(!que.empty())
32     {
33         node q=que.front();que.pop();
34         if(q.time>T) return false;
35         if(maze[q.order][q.x][q.y]=='P') 
36             return true;//找到公主
37         for(int p=0;p<4;p++)//前后左右移动 
38         {
39             int ord=q.order,xx=q.x+dx[p],yy=q.y+dy[p];
40             if(xx<0||xx>=N||yy<0||yy>=M) continue;//超出边界
41             if(maze[ord][xx][yy]=='*') continue;//撞墙
42             if(isvisit[ord][xx][yy]) continue; //访问过 
43             isvisit[ord][xx][yy]=1;//标记状态 
44             if(maze[ord][xx][yy]=='#')//时空传送 
45                 {
46                         ord=!ord;//地图种类由0变为1或由1变为0 
47                     if(maze[ord][xx][yy]=='*') continue;//撞墙
48                     if(maze[ord][xx][yy]=='#') continue;//无限循环
49                     if(isvisit[ord][xx][yy]) continue;//访问过 
50                     isvisit[ord][xx][yy]=1;//标记状态 
51                 }
52             que.push(node(ord,xx,yy,q.time+1));//时间+1，存入队列 
53         } 
54     }
55     return false;//不能找到公主 
56 }
57 int main()
58 {
59     int C;
60     cin>>C;
61     while(C--)
62     {
63         int T;
64         cin>>N>>M>>T;
65         for(int k=0;k<2;k++)
66             for(int i=0;i<N;i++)
67                 for(int j=0;j<M;j++)
68                     cin>>maze[k][i][j];
69         
70         if(bfs(T)) cout<<"YES"<<endl;
71         else cout<<"NO"<<endl;  
72     } 
73 }
74

View Code