HDU - 2102 A计划

本文主要是介绍HDU - 2102 A计划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题： 传送门
题意： 地图有两层，除了墙壁（*），空地（.），起点（S），终点（P）外，还有传送门（#），走到传送门上时，会到达另一层的对应位置，不耗费时间，除此之外每移动一格花费一个时间，问最短时间是不是小于等于T
思路： 直接bfs，只不过数组开三维的
注意：

1. 当从队列里面拿出新的点时，如果这个点是传送门，那么直接令
   u.f = !u.f;，如果传送门对面也是传送门，那么就不要过去了，因为会陷入死循环，还有对面是墙壁的情况也不行，直接continue;

2. 当从队列里面拿出新的点时，判断出口的if要写在处理传送门的后面，要不然会出现传送过去是终点，但是bfs找不到的情况

Code：

#include<iostream>
#include<queue>
#include<cstring>typedef long long ll;
using namespace std;char mp[2][17][17];
bool vis[2][17][17];
int n, m, t;
int dx[] = {-1,0,0,1};
int dy[] = {0,-1,1,0};struct node {int x, y, f, step;node (int xx, int yy, int ff, int ss):x(xx), y(yy), f(ff), step(ss) {}//写构造函数,方便初始化
};bool is_in(int x, int y) {//判断是否越界if (x>=0&&x<n&&y>=0&&y<m)return true;elsereturn false;
}
int bfs(int x, int y, int f) {queue<node> q;node d(x, y, f, 0);q.push(d);while (!q.empty()) {node u = q.front();q.pop();if (mp[u.f][u.x][u.y] == '#') {//处理传送门u.f = !u.f;vis[u.f][u.x][u.y] = true;if (mp[u.f][u.x][u.y] == '#' || mp[u.f][u.x][u.y] == '*')continue;}if (mp[u.f][u.x][u.y] == 'P') {//出口return u.step;}for (int i=0;i<4;i++) {int nx = u.x + dx[i], ny = u.y + dy[i];if (is_in(nx, ny) && mp[u.f][nx][ny] != '*' && !vis[u.f][nx][ny]) {q.push(node(nx, ny, u.f, u.step+1));vis[u.f][nx][ny] = true;}}}return -1;
}int main()
{ios::sync_with_stdio(false);//关闭与stdio的同步,加速IOint T;cin>>T;while (T--) {memset(vis, 0, sizeof(vis));cin>>n>>m>>t;for (int a=0;a<2;a++)for (int i=0;i<n;i++){cin>>mp[a][i];}vis[0][0][0]=true;int stp = bfs(0, 0, 0);//cout<<stp<<endl;if (stp <= t && stp != -1)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return 0;
}

ps：因为这个肺炎，苟在家里哪里也去不了，蓝瘦啊

这篇关于HDU - 2102 A计划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---