JZOJ-5781【秘密通道 】solution
题面
Description
有一副$nm$的地图，有$nm$块地，每块是下列四种中的一种：
墙：用#表示，墙有4个面，分别是前面，后面，左面，右面。
起点：用C表示，为主角的起点，是一片空地。
终点：用F表示，为主角的目的地，是一片空地。
空地：用 . 表示。
其中除了墙不能穿过，其他地方都能走。
主角有以下3种操作：
1.移动到相邻的前后左右的地方，花费一个单位时间。
2.向前后左右其中一个方向发射子弹，子弹沿直线穿过，打在最近的一堵墙的一面，然后墙的这面就会形成一个开口通往秘密通道。同一时间最多只能有两个开口，若出现有3个开口，出现时间最早的开口会立即消失。该操作不用时间。
3.可以从一个与开口相邻的空地跳进去，进入秘密通道，从另外一个开口正对的空地跳出来。这个过程花费一个单位时间。
地图四周都是墙，问主角最少用多少时间从C走到F。C和F只会出现一次。
Input
第一行输入两个正整数$n$，$m$。
接下来$n$行，每行$m$个字符描述地图。
Output
输出1个整数，表示最短时间完成路途。如果无解输出nemoguce
Sample Input
Input 1
4 4
####
#.F#
#C.#
####
Input 2
6 8
########
#.##..F#
#C.##..#
#..#...#
#.....##
########
Input 3
4 5
#####
#C#.#
###F#
#####
Sample Output
Output 1
2
Output 2
4
Output 3
nemoguce
Data Constraint
对于50%的数据，$4≤ n,m≤ 15$。
对于100%的数据，$4≤ n,m≤ 500$。
Hint
总共用到8次操作，时间之和为4。如下图所示（图被吃掉了）
1.向左射一枪，在(3,1)的右面出现开口。
2.向下射一枪，在(6,2)的上面出现开口。
3.向左从(3,1)进入秘密通道，从(6,2)中出来，到达(5,2)。用1单位时间。
4.向右射一枪，在(5,7)的左面出现开口，(3,1)右面的开口消失。
5.走进(6,2)的开口，出来到(5,6)。用1单位时间。
6.向上射一枪，在(1,6)的下面出现开口。
7.经过秘密通道，走到(2,6)。用1单位时间。
8.走到终点。用1单位时间。
分割线
思路
这个题乍一眼看上去就像是一个BFS有没有，但是BFS是错误的（虽然数据水到BFS都可以那70分）
至于为什么BFS是错误的，用一个很形象的样例来解释（本人说不清）
#########
#......##
#......##
#......##
#.......#
#.....S.#
#.......#
#.......#
#.......#
#########
这里小X可以先向上和向右打一个子弹，再向右跑到边框，瞬移到上面
手动模拟小X在迷宫中的移动过程，可以发现以下结论
1.这里发射子弹并不能穿墙，所以如果小X在图中与终点不连通的话，那么永远无法到达终点，输出那串字符
2.小X可以在某一个结点$(x_i,y_i)$向周围的某两堵墙分别打一个子弹，再移动到某一个开口处，花1份时间移动到另一个开口，因此小X可以在移动到最近的墙之后花一份时间瞬移到另一个很远的墙边上。
想到这里有没有一点思路了呢？
正解做法
在某一个不是墙的结点$(x_i,y_i)$，向它周围的4个（不是墙的）上下左右结点连一条权值为1的边，向它上下左右4个方向向墙旁边的那个点连一条权值为结点$(x_i,y_i)$与四周墙的最近距离（注意是墙的！！！）的边，模型瞬间转化为了最短路，很神奇有没有！！！
这里最短路可以有很多种实现方式，据说SPFA，Dij+Heap等，不建议使用SPFA因为可能会被卡掉（虽然这里不会）
下面贴上本人巨丑的玄学Dij+Heap代码
Code
294ms,49.33MB
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
char map[503][503];
int n,m;
struct Edge{
int si,sj,ti,tj,nxt,w;
}edge[2000005];
int si,ti,sj,tj;
int head[503][503],book[503][503],dis[503][503],tot=0;
const int di[4]={0,0,1,-1},dj[4]={1,-1,0,0};
priority_queue<pair<int,pair<int,int> > > hep;
//queue< pair<int,int> > q;
int gmin(int a,int b){return a<b?a:b;}
void add(int sti,int stj,int toi,int toj,int we){
edge[tot].si=sti;
edge[tot].sj=stj;
edge[tot].ti=toi;
edge[tot].tj=toj;
edge[tot].w=we;
edge[tot].nxt=head[sti][stj];
head[sti][stj]=tot;
tot++;
}
int main(){
freopen("portal.in","r",stdin);
freopen("portal.out","w",stdout);
memset(head,-1,sizeof(head));
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",map[i]);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
if(map[i][j]=='C'){
si=i;sj=j;
}
if(map[i][j]=='F'){
ti=i;tj=j;
}
}
for(int i=1;i<n-1;i++)
for(int j=1;j<m-1;j++)
if(map[i][j]!='#'){
int ni,nj,minn=inf;
for(int k=0;k<4;k++){
ni=i+di[k];
nj=j+dj[k];//cout<<i<<' '<<j<<' '<<k<<endl;
if(map[ni][nj]!='#')
add(i,j,ni,nj,1);
}
int nti[4],ntj[4];
for(int k=0;k<4;k++){//cout<<1<<endl;
ni=i;nj=j;int cnt=0;
while(map[ni][nj]!='#'){
ni+=di[k];nj+=dj[k];cnt++;
}
ni-=di[k];nj-=dj[k];
nti[k]=ni;ntj[k]=nj;
minn=gmin(minn,cnt);
}
for(int k=0;k<4;k++)
add(i,j,nti[k],ntj[k],minn);
}
memset(dis,0x3f,sizeof(dis));
memset(book,0,sizeof(book));
hep.push(make_pair(0,make_pair(si,sj)));
dis[si][sj]=0;
/*q.push(make_pair(si,sj));
while(!q.empty()){
int ni=q.front().first,nj=q.front().second;
book[ni][nj]=0;
q.pop();
for(int i=head[ni][nj];i!=-1;i=edge[i].nxt){
int nti=edge[i].ti,ntj=edge[i].tj,w=edge[i].w;
if(dis[nti][ntj]>dis[ni][nj]+w){
dis[nti][ntj]=dis[ni][nj]+w;
if(!book[nti][ntj]){
q.push(make_pair(nti,ntj));
book[nti][ntj]=1;
}
}
}
}*/
while(!hep.empty()){
int ni=hep.top().second.first,nj=hep.top().second.second;//cout<<"pp"<<endl;
hep.pop();
if(book[ni][nj]==0){
book[ni][nj]=1;
for(int i=head[ni][nj];i!=-1;i=edge[i].nxt){
int nti=edge[i].ti,ntj=edge[i].tj,w=edge[i].w;
if(dis[nti][ntj]>dis[ni][nj]+w){
dis[nti][ntj]=dis[ni][nj]+w;
hep.push(make_pair(0-dis[nti][ntj],make_pair(nti,ntj)));
}
}
}
}
if(dis[ti][tj]==inf)
printf("nemoguce\n");
else
printf("%d\n",dis[ti][tj]);
//for(int i=0;i<tot;i++){
// cout<<i<<' '<<edge[i].si<<' '<<edge[i].sj<<' '<<edge[i].ti<<' '<<edge[i].tj<<' '<<edge[i].w<<endl;
//}
//for(int i=0;i<n;i++){
// for(int j=0;j<m;j++){
// cout<<map[i][j]<<' ';
// }cout<<endl;
//}
return 0;
}