首页 > 代码库 > HDU 2102 A计划
HDU 2102 A计划
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2102
题解:
BFS+剪枝
1.题意不是很清楚,不太清楚S是否一定是(0,0,0),所以这里做了一次查找;
2.对于传送门的问题,如果两个传送门相对,那么骑士一定会被传送门华丽丽地玩死了;
3.剪枝,这里的剪枝由于两层之间传送不消耗时间,所以我们只需要求:T(当前位置)+DIS(公主位置-当前位置)<=T才能继续进行,否则就要被剪掉
代码:
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define Lowbit(x) ((x)&(-(x))) #define ll long long #define mp make_pair #define ff first #define ss second #define pb push_back #define mod 10000007 //#define LOCAL #define MAXN 100010 #define INF 1e9 #define Max 100010 int ty[]={0,1,0,-1}; int tz[]={1,0,-1,0}; char str[2][15][15]; bool visit[2][15][15]; int N,M,T; typedef struct node{ int x,y,z; int cost; }NODE; bool check(int &x,int &y,int &z){ if(y<0||y>=N||z<0||z>=M||str[x][y][z]=='*'||visit[x][y][z]) return false; visit[x][y][z] = true; if(str[x][y][z]=='#') if(str[x^1][y][z]=='*'||str[x^1][y][z]=='#') return false; else x^=1; //传送门进行层传递 visit[x][y][z] = true; return true; } int main(){ int C; scanf("%d",&C); while(C--){ scanf("%d%d%d", &N, &M, &T); int i,j,k; for(i=0; i<2; ++i){ for(j=0; j<N; ++j) scanf("%s", str[i][j]); } NODE now; NODE target; //查找'S'\'P'点的位置 for(i=0; i<2; ++i){ for(j=0; j<N; ++j){ for(k=0; k<M; ++k){ if(str[i][j][k]=='S'){ now.x = i; now.y = j; now.z = k; } if(str[i][j][k]=='P'){ target.x = i; target.y = j; target.z = k; } } } } //BFS memset(visit, false, sizeof(visit)); now.cost = 0; queue<NODE> que; que.push(now); visit[now.x][now.y][now.z] = true; bool flag = false; while(que.size()){ now = que.front(); que.pop(); if(now.cost>T) break; if(now.x==target.x&&now.y==target.y&&now.z==target.z){ flag = true; break; } NODE next; for(i=0; i<4; ++i){ next.x = now.x; next.y = now.y+ty[i]; next.z = now.z+tz[i]; next.cost = now.cost+1; if(check(next.x,next.y,next.z)){ //剪枝 if(next.cost+ abs(target.y-next.y)+abs(target.z-next.z)>T) continue; que.push(next); } } } printf("%s\n", flag?"YES":"NO"); } return 0; }
HDU 2102 A计划
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。