[USACO11OPEN]Corn Maze S
题面翻译
奶牛们去一个 $N\times M$ 玉米迷宫,$2 \leq N \leq 300,2 \leq M \leq300$。
迷宫里有一些传送装置,可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用。
如果一头奶牛处在这个装置的起点或者终点,这头奶牛就必须使用这个装置。
玉米迷宫除了唯一的一个出口都被玉米包围。
迷宫中的每个元素都由以下项目中的一项组成:
- 玉米,
#
表示,这些格子是不可以通过的。 - 草地,
.
表示,可以简单的通过。 - 传送装置,每一对大写字母 $\tt{A}$ 到 $\tt{Z}$ 表示。
- 出口,
=
表示。 - 起点,
@
表示
奶牛能在一格草地上可能存在的四个相邻的格子移动,花费 $1$ 个单位时间。从装置的一个结点到另一个结点不花时间。
题目描述
This past fall, Farmer John took the cows to visit a corn maze. But this wasn’t just any corn maze: it featured several gravity-powered teleporter slides, which cause cows to teleport instantly from one point in the maze to another. The slides work in both directions: a cow can slide from the slide’s start to the end instantly, or from the end to the start. If a cow steps on a space that hosts either end of a slide, she must use the slide.
The outside of the corn maze is entirely corn except for a single exit.
The maze can be represented by an N x M (2 <= N <= 300; 2 <= M <= 300) grid. Each grid element contains one of these items:
* Corn (corn grid elements are impassable)
* Grass (easy to pass through!)
* A slide endpoint (which will transport a cow to the other endpoint)
* The exit
A cow can only move from one space to the next if they are adjacent and neither contains corn. Each grassy space has four potential neighbors to which a cow can travel. It takes 1 unit of time to move from a grassy space to an adjacent space; it takes 0 units of time to move from one slide endpoint to the other.
Corn-filled spaces are denoted with an octothorpe (#). Grassy spaces are denoted with a period (.). Pairs of slide endpoints are denoted with the same uppercase letter (A-Z), and no two different slides have endpoints denoted with the same letter. The exit is denoted with the equals sign (=).
Bessie got lost. She knows where she is on the grid, and marked her current grassy space with the ‘at’ symbol (@). What is the minimum time she needs to move to the exit space?
输入格式
第一行:两个用空格隔开的整数 $N$ 和 $M$。
第 $2\sim N+1$ 行:第 $i+1$ 行描述了迷宫中的第 $i$ 行的情况(共有$M$个字符,每个字符中间没有空格)。
输出格式
一个整数,表示起点到出口所需的最短时间。
样例 #1
样例输入 #1
5 6
###=##
#.W.##
#.####
#.@W##
######
样例输出 #1
3
提示
例如以下矩阵,$N=5,M=6$。
###=##
#.W.##
#.####
#.@W##
######
唯一的一个装置的结点用大写字母 $\tt{W}$ 表示。
最优方案为:先向右走到装置的结点,花费一个单位时间,再到装置的另一个结点上,花费 $0$ 个单位时间,然后再向右走一个,再向上走一个,到达出口处,总共花费了 $3$ 个单位时间。
看法
这题非常坑,只是传统BFS加个传送门,让这个题难度倍增,调了几个小时,服了
首先看坑点
传送点只是一个中介点
# # # # # # = # #
# . . . . . . # #
# # # A # # # # #
# @ . . # A . . #
# # # # # # # # #
这说明存在正解路径是经过传送门走一步又回来才能到达终点
这个传送门性质特殊
这就需要考虑怎么判重,防止多次无用的进入传送门
尝试这么做:
可以发现传送门只会进一次,之后再尝试进入传送门的路径都不是最短路
那么我们不管传送前那个点,让它dist还是-1(用来判重),然后给传送后的位置设置距离后加入队列行不行呢
实际上不行,问题很隐蔽,因为可能在传送后位置还在队列没出来时候,发生了如下事情:
(注意考虑bfs队列位置对应距离可能存在相差为1的两个值)
有路径进入传送后位置,把它当作起跳点传送,这样落脚点(就是原来传送前那个dist是-1的位置)的距离被更新成正的
之后有路径进入传送前位置(这个路径更新前距离比之前的大1),然后传送后的位置距离被设置为比原来多1的结果
这样在它出来时候,它的距离不是原来和他对应的那个值,这样就产生了错误,具体来说:
1.bfs角度:不能保证bfs中一旦进入队列那么该点入度已经为0的特点
2.根据dijk最短路原理,先从队列里出来的应该是距离最小的点,而在它出来时,比它本身的值多1,这样求的最短路很可能就是错的(只要队列里还有和它本来应该等于的距离相等的位置)
正确做法:
光dist是不能判重的,还需要一个额外的判重数组,它只给传送前位置标记防止再进入,而不能都标记(因为可能进传送门又出来,要保证回得去)
AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
#define speed_up ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define x first
#define y second
const int N=310;
int n,m;
char g[N][N];
ll dist[N][N];
bool gone[N][N];
pii st;
vector<pii> fly[26];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
ll bfs(){
dist[st.x][st.y]=0;
gone[st.x][st.y]= true;
queue<pii> q;
q.push(st);
while(!q.empty()){
auto t=q.front();
int x=t.x,y=t.y;
q.pop();
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<0 || nx>=n || ny<0 || ny>=m || g[nx][ny]=='#')continue;
if(gone[nx][ny])continue;
int xx,yy;
gone[nx][ny]= true;
if(isalpha(g[nx][ny])){
int seq=g[nx][ny]-'A';
pii a=fly[seq][0],b=fly[seq][1];
if(make_pair(nx,ny) == a)xx=b.x,yy=b.y;
else xx=a.x,yy=a.y;
dist[xx][yy]=dist[x][y]+1;
q.push({xx,yy});
}
else {
q.push({nx,ny});
dist[nx][ny]=dist[x][y]+1;
if(g[nx][ny]=='=')return dist[nx][ny];
}
}
}
}
int main(){
cin>>n>>m;
memset(dist,-1,sizeof dist);
for(int i=0;i<n;i++){
cin>>g[i];
for(int j=0;j<m;j++){
if(g[i][j]=='@')st={i,j};
if(isalpha(g[i][j]))fly[g[i][j]-'A'].push_back({i,j});
}
}
cout<<bfs();
return 0;
}
总结
可能只用dist判重算是偷懒了,如果习惯做bfs加上额外的一个判重数组可能这个题就轻松水过去了,正因为执着于用dist判重才花费了好多时间,这事具有两面性,多个额外判重数组有时候未必会更坏