201604-4游戏（BFS+优先队列/三维BFS）
问题描述
| 试题编号： | 201604-4 |
| 试题名称： | 游戏 |
| 时间限制： | 1.0s |
| 内存限制： | 256.0MB |
| 问题描述： |
问题描述 小明在玩一个电脑游戏，游戏在一个n×m的方格图上进行，小明控制的角色开始的时候站在第一行第一列，目标是前往第n行第m列。 输入格式 输入的第一行包含三个整数n, m, t，用一个空格分隔，表示方格图的行数n、列数m，以及方格图中有危险的方格数量。 输出格式 输出一个整数，表示小明最快经过几个时间单位可以过关。输入数据保证小明一定可以过关。 样例输入 3 3 3 样例输出 6 样例说明 第2行第1列时刻1是危险的，因此第一步必须走到第1行第2列。 评测用例规模与约定 前30%的评测用例满足：0 < n, m ≤ 10，0 ≤ t < 99。 |
求解思路：
刚看到这道题的时候，心想：这不就是BFS么，easy one.......，然后就直接用BFS做，马上20分打脸。这道题与普通BFS的区别在于：普通BFS访问过的节点是不会再去访问的，而在本题中，由于处于危险中的节点并不是一直处于危险中，只是某一个时间段，因此就会出现这种情况：当小明走到某一点时，与该点相邻的一个节点处于危险状态，但仅仅有1个时间单位的危险时间，并且这个相邻点的下一个相邻点就是终点（只是举了一种比较极端的情况），而其余节点均不在危险状态，但是这些节点的相邻节点均不是终点，并且这些节点会把小明引到远离终点的方向。如下图：
如果用原版BFS，那么小明知道3号节点当前危险，因此将3号标记为已访问，之后就不会再去访问，故，小明会选择2号或是4号节点（选哪个取决于转移数组的顺序），假如小明选择了1号节点，该节点当前安全，故小明站到了1号节点上，时间来到了1s，然后与1号节点相邻的4号节点在下一秒（2s）是危险的，故小明不会选择4号，而是选择另外两个相邻节点（图中没有给出），不论小明选择了哪个节点，他最终到达终点的时间肯定超过了3s。回过头来想，如果小明在最初的位置逗留1s，那么这时3号节点就安全了，小明可以站在3号节点上，然后再经过1s小明就到达终点了，用时为3s，显然更短。可见，原版的BFS失效了，这是因为无法选择曾经危险的节点。
因此需要对原版BFS进行修改，需要增加原地踱步处理，由于当前节点+1s然后进行判断，这是在看能不能直接走，所以可以让当前节点+2s后直接进入队列，而不进行判断，这就是踱步，有人可能会问：你这不是才等待1s么，如果节点的危险时间不止1s咋整？嗯，注意，我们+2s后直接进入队列，也就是说，这种情况还可以再次被取出来，然后在此基础上+2s进队列，这就已经将需要继续等待的情况放入队列中了。但是我们对原版BFS的改造还没结束，原版BFS用到的队列是普通的队列，先进先出，那么就有可能处于队列中的之前处在等待状态的情况更早的到达终点，而队头情况尚未到达，因此需要选用优先队列，将当前时间最小的情况放在队列的队头，这样就能保证每次取出的情况都是当前最早的。那么我们肯定会疑惑，原版的BFS怎么不用考虑这个问题？其实，区别就在于需不需要踱步，原版情况是：这个节点不能访问就一定不会再去访问，没有回溯，相等于图的层序遍历，而时间t随着层数增加而增加，因此是递增的。而当前这种情况存在回溯，那么就有可能在回溯的过程中，出现时间更小的分支。
综上所述：原版的BFS被修改为：+2s逗留处理以及用优先队列选择当前最小t的情况
代码（BFS+优先队列）：
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
struct Node {
long long left, right;
Node () { left = right = 0x3f3f3f3f; }
};
struct Time {
long long x, y, time;
bool operator < (const Time &A)const{//重载小于号，为了构造小根堆
return time>A.time;
}
};
long long n, m, t, vis[105][105] = {};
long long move[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
Node map[105][105];
long long BFS()
{
priority_queue<Time> Q;//优先队列
Time tmp;
tmp.x=1;
tmp.y=1;
tmp.time=0;
Q.push(tmp);
vis[1][1] = 1;
while (1) {
long long x = Q.top().x, y = Q.top().y, time = Q.top().time;
if (x == n && y == m) return time;
Q.pop();
Time ttmp;
ttmp.x=x;
ttmp.y=y;
ttmp.time=time+2;//+2s踱步
Q.push(ttmp);//将踱步的情况放入队列中
if (time >= map[x][y].left && time <= map[x][y].right) continue;//处于危险状态
for (long long i = 0; i < 4; ++i) {
long long xx = x + move[i][0], yy = y + move[i][1];
if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
if (time + 1 >= map[xx][yy].left && time + 1 <= map[xx][yy].right) continue;
if (vis[xx][yy]) continue;
vis[xx][yy] = true;
Time ttmp1;
ttmp1.x=xx;
ttmp1.y=yy;
ttmp1.time=time+1;
Q.push(ttmp1);
}
}
}
int main()
{
cin >> n >> m >> t;
for (long long i = 0, u, v, l, r; i < t; ++i) {
cin >> u >> v >> l >> r;
map[u][v].left = l;
map[u][v].right = r;
}
long long ans = BFS();
cout << ans;
}注：此代码选自****博主：姬小野
网上大佬普遍给出的是另一种方法：三维BFS
所谓三维，就是在横纵坐标的基础上又增加了时间这一维度，上面我们讨论过，这道题的关键就是某段时间不安全的节点在之后有可能会被回溯到。那么我们为何非要把不同时间的节点看做是同一个节点呢？我们可以把不同时间的节点看做是不同的节点，这样所有的情况就都有被遍历的能力，这样就成功的将这道题转化为普通的BFS了。
代码（三维BFS）：
#include<iostream>
#include<queue>
using namespace std;
typedef struct E{
int x,y;
int t;
bool operator <(const E &A)const{
return t>A.t;
}
}E;
bool mark[101][101][500]={};
int go[][2]={
1,0,
-1,0,
0,1,
0,-1,
};
priority_queue<E> Q;
long long BFS(int n,int m)
{
while(!Q.empty())
{
E now=Q.top();
Q.pop();
for(int i=0;i<4;i++)
{
int nx=now.x+go[i][0];
int ny=now.y+go[i][1];
int t=now.t+1;
if(nx>n||ny>m||nx<1||ny<1) continue;
if(mark[nx][ny][t]) continue;
E tmp;
tmp.x=nx;
tmp.y=ny;
tmp.t=t;
Q.push(tmp);
mark[nx][ny][t]=true;
if(nx==n&&ny==m) return t;
}
}
}
int main()
{
int n,m,t,r,c,a,b;
scanf("%d%d%d",&n,&m,&t);
while(t--)
{
scanf("%d%d%d%d",&r,&c,&a,&b);
for(a;a<=b;a++)
{
mark[r][c][a]=true;//不安全时刻的节点直接设置为已访问，因为即使遍历到这些节点，也不会将这些节点选中，索性就不去遍历它们
}
}
E first;
first.x=1;
first.y=1;
first.t=0;
Q.push(first);
long long res=BFS(n,m);
printf("%lld\n",res);
return 0;
}注意：在读入节点数据时，我们将不安全时刻的节点直接设置为已遍历，这是因为即使遍历到这些节点，也不会将这些节点选中，索性就不去遍历它们 ，这是BFS的一种简化方式。
运行结果：