问题描述
CYJ想找到他的小伙伴FPJ，.CYJ和FPJ现在位于一个房间里,这个房间的布置可以看成一个N行M列的矩阵,矩阵内的每一个元素会是下列情况中的一种:
- 障碍区域—这里有一堵墙(用‘#’表示).
- 这是CYJ最开始在的区域(用‘C’表示).
- 这是FPJ在的区域(用‘F’表示).
- 空区域(用‘.’表示).
CYJ携带了一个所谓传送枪的东西,这是一把可以创造传送门的枪械,在每一次行动中,他可以选择下列操作中的一项: - 移向一个相邻的格子中(上,下,左,右,不能移到墙在的格子里).这个操作要消耗一个单位的时间.
- 转向一个墙(不需要相邻,只需面向即可),向其发射传送门,传送门会留在墙内面向你的地方(至多只能同时存在两扇传送门)，若墙上已经有两扇传送门，而你发射了第三扇,那么最初发射的那一扇会消失。同时,你无法在一个位置制造两扇传送门（这个操作不会耗费时间）。
- 如果他与一块墙壁相邻且面前有一扇传送门,那么他可以移动到另一扇传送门前方的格子。这个操作会耗费一个单位的时间.
CYJ想要知道自己最少需要多少时间才能够从起点(‘C’)到达终点(‘F’).
请注意:我们保证地图边缘会是一圈墙壁且一定存在‘C’,‘F’.
输入
第一行输入两个正整数 N 和 M ,(4 ≤ N,M ≤ 500).表示地图大小。
接下来的N行每行一个长度为M的字符串.表示地形。
输出
你需要输出最少的到达终点的时间,如果不能到达请输出”no”。
先BFS搜出每个点到墙(或到旁边有墙的点)的距离，同时用这个距离建图，建完图跑diji或spfa得出正解
#include<bits/stdc++.h>
using namespace std;
const int Maxn = 505;
const int MX = 3e5+5;
const int inf = 1e9;
int N,M,S,T,cnt;
int md[Maxn][Maxn],Lm[Maxn][Maxn],Rm[Maxn][Maxn];
int Dm[Maxn][Maxn],Um[Maxn][Maxn],hed[MX];
int nxt[MX<<4],to[MX<<4],len[MX<<4],dis[MX];
char mp[Maxn][Maxn];
struct data{
int x , y;
bool operator <(const data &A) const{
return y > A.y;
}
};
queue<data>Q;
inline int id(int x,int y){return (x - 1)*M + y;}
void inc(int x,int y,int d){
if(mp[x][y] == '.' && !md[x][y])
md[x][y] = d , Q.push((data){x,y});
}
void Bfs(){
while(!Q.empty()){
int x = Q.front().x,y = Q.front().y;
Q.pop();
inc(x - 1 , y , md[x][y] + 1);
inc(x , y - 1 , md[x][y] + 1);
inc(x + 1 , y , md[x][y] + 1);
inc(x , y + 1 , md[x][y] + 1);
}
}
void Adg(int x,int y,int l){
nxt[++cnt] = hed[x]; to[cnt] = y;
hed[x] = cnt; len[cnt] = l;
}
void Addedge(int x,int y,int l){
Adg(x , y , l); Adg(y , x , l);
}
void init(){
for(int i = 1 ; i <= N ; ++i)
for(int j = 1 ; j <= M ; ++j) if(mp[i][j] == '.'){
if(mp[i][j-1] == '#') Lm[i][j] = id(i , j);
else Lm[i][j] = Lm[i][j - 1];
if(mp[i-1][j] == '#') Um[i][j] = id(i , j);
else Um[i][j] = Um[i - 1][j];
}
for(int i = N ; i ; --i)
for(int j = M ; j ; --j) if(mp[i][j] == '.'){
if(mp[i][j+1] == '#') Rm[i][j] = id(i,j);
else Rm[i][j] = Rm[i][j + 1];
if(mp[i+1][j] == '#') Dm[i][j] = id(i,j);
else Dm[i][j] = Dm[i + 1][j];
}
}
void Build(){
for(int i = 1 ; i <= N ; ++i)
for(int j = 1 ; j <= M ; ++j) if(mp[i][j] == '.'){
if(mp[i][j + 1] == '.') Addedge(id(i,j),id(i,j+1),1);
if(mp[i + 1][j] == '.') Addedge(id(i,j),id(i+1,j),1);
if(Lm[i][j] != id(i , j)) Adg(id(i,j),Lm[i][j],md[i][j]);
if(Rm[i][j] != id(i , j)) Adg(id(i,j),Rm[i][j],md[i][j]);
if(Um[i][j] != id(i , j)) Adg(id(i,j),Um[i][j],md[i][j]);
if(Dm[i][j] != id(i , j)) Adg(id(i,j),Dm[i][j],md[i][j]);
}
}
void Dijkstra(){
priority_queue<data>PQ;
for(int i = 1 ; i <= N*M ; ++i)
dis[i] = inf;
dis[S] = 0; PQ.push((data){S,dis[S]});
while(!PQ.empty()){
int x = PQ.top().x,L = PQ.top().y;
PQ.pop();
if(L > dis[x]) continue;
for(int i = hed[x],v ; i ; i = nxt[i])
if(dis[v = to[i]] > dis[x] + len[i]){
//if(v == T) printf("%d
",x);
dis[v] = dis[x] + len[i];
PQ.push((data){v,dis[v]});
}
}
}
int main(){
freopen("cell.in","r",stdin);
freopen("cell.out","w",stdout);
scanf("%d%d",&N,&M);
for(int i = 1 ; i <= N ; ++i)
scanf("%s" , mp[i] + 1);
for(int i = 1 ; i <= N ; ++i)
for(int j = 1 ; j <= M ; ++j){
if(mp[i][j] == 'C') mp[i][j] = '.',S = id(i,j);
if(mp[i][j] == 'F') mp[i][j] = '.',T = id(i,j);
}
for(int i = 1 ; i <= N ; ++i)
for(int j = 1 ; j <= M ; ++j)
if(mp[i][j] == '#') Q.push((data){i,j});
Bfs(); init();
Build(); Dijkstra();
if(dis[T] != inf) printf("%d
",dis[T]);
else printf("no
");
return 0;
}