首页 > 代码库 > HDU 2102 A计划
HDU 2102 A计划
A计划
Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 210264-bit integer IO format: %I64d Java class name: Main
可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。
现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S（0，0，0），公主的位置用P表示，时空传输机用#表示，墙用*表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。
现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是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
15 5 14S*#*..#........****....#...*.P#.*..***.....*.*.#..
Sample Output
YES
Source
HDU 2007-6 Programming Contest
解题：bfs搜索
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 struct node {18 int x,y,z,step;19 node(int a = 0,int b = 0,int c = 0,int d = 0) {20 x = a;21 y = b;22 z = c;23 step = d;24 }25 };26 queue<node>q;27 const int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};28 bool vis[2][25][25];29 char mp[2][25][25];30 int n,m,t;31 bool bfs() {32 while(!q.empty()) q.pop();33 memset(vis,false,sizeof(vis));34 q.push(node(0,1,1,0));35 vis[0][1][1] = true;36 while(!q.empty()) {37 node now = q.front();38 q.pop();39 for(int i = 0; i < 4; i++) {40 int x = now.x;41 int y = now.y+dir[i][0];42 int z = now.z+dir[i][1];43 if(mp[x][y][z] == ‘*‘ || vis[x][y][z]) continue;44 vis[x][y][z] = true;45 if(mp[x][y][z] == ‘#‘) {46 if(x) x = 0;47 else x = 1;48 }49 if(now.step+1 > t) return false;50 if(mp[x][y][z] == ‘P‘) return true;51 q.push(node(x,y,z,now.step+1));52 }53 }54 return false;55 }56 int main(){57 int ks,i,j,k;58 scanf("%d",&ks);59 while(ks--){60 memset(mp,‘*‘,sizeof(mp));61 scanf("%d %d %d",&n,&m,&t);62 for(i = 0; i < 2; i++){63 for(j = 1; j <= n; j++)64 for(k = 1; k <= m; k++)65 cin>>mp[i][j][k];66 }67 for(i = 1; i <= n; i++){68 for(j = 1; j <= m; j++){69 if(mp[0][i][j] == ‘#‘ && mp[1][i][j] == ‘#‘)70 mp[0][i][j] = mp[1][i][j] = ‘*‘;71 if(mp[0][i][j] == ‘#‘ && mp[1][i][j] == ‘*‘)72 mp[0][i][j] = ‘*‘;73 if(mp[0][i][j] == ‘*‘ && mp[1][i][j] == ‘#‘)74 mp[1][i][j] = ‘*‘;75 }76 }77 bfs()?puts("YES"):puts("NO");78 }79 return 0;80 }
dfs版，貌似比bfs难写一点！
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int dir[4][2] = {0,-1,-1,0,1,0,0,1};18 int ex,ey,ez,n,m,t;19 char mp[2][25][25];20 bool dfs(int step,int x,int y,int z,int pre) {21 if(step <= t && mp[x][y][z] == ‘P‘) return true;22 if(abs(y-ey)+abs(z-ez)+step > t) return false;23 if(step >= t) return false;24 for(int i = 0; i < 4; i++) {25 int tx = x;26 int ty = y+dir[i][0];27 int tz = z+dir[i][1];28 if(i == pre || mp[tx][ty][tz] == ‘*‘) continue;29 if(mp[tx][ty][tz] == ‘#‘) {30 if(tx) tx = 0;31 else tx = 1;32 if(dfs(step+1,tx,ty,tz,-1)) return true;33 } else if(dfs(step+1,tx,ty,tz,3-i)) return true;34 }35 return false;36 }37 int main() {38 int ks,i,j,k;39 scanf("%d",&ks);40 while(ks--) {41 memset(mp,‘*‘,sizeof(mp));42 scanf("%d %d %d",&n,&m,&t);43 for(i = 0; i < 2; i++) {44 for(j = 1; j <= n; j++)45 for(k = 1; k <= m; k++)46 cin>>mp[i][j][k];47 }48 for(i = 1; i <= n; i++) {49 for(j = 1; j <= m; j++) {50 if(mp[0][i][j] == ‘P‘){51 ex = 0;52 ey = i;53 ez = j;54 }55 if(mp[1][i][j] == ‘P‘){56 ex = 1;57 ey = i;58 ez = j;59 }60 if(mp[0][i][j] == ‘#‘ && mp[1][i][j] == ‘#‘)61 mp[0][i][j] = mp[1][i][j] = ‘*‘;62 if(mp[0][i][j] == ‘#‘ && mp[1][i][j] == ‘*‘)63 mp[0][i][j] = ‘*‘;64 if(mp[0][i][j] == ‘*‘ && mp[1][i][j] == ‘#‘)65 mp[1][i][j] = ‘*‘;66 }67 }68 if(t > max(n,m)*3) t = max(n,m)*3;69 dfs(0,0,1,1,-2)?puts("YES"):puts("NO");70 }71 return 0;72 }
i
1 if(abs(y-ey)+abs(z-ez)+step > t) return false;//A*评估，小小的剪枝优化2 3 if(t > max(n,m)*3) t = max(n,m)*3;//能防止TLE
HDU 2102 A计划
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。