正題

題目鏈接:https://www.luogu.org/problem/P4442

---

題目大意

一個(gè)$n?m$的矩陣，有墻。然后每次可以上下左右或者走入傳傳送門(mén)。當(dāng)然也可以像上下左右任意一個(gè)方向發(fā)射傳送門(mén)(直到碰到墻)但這并不會(huì)消耗時(shí)間。

求起點(diǎn)到終點(diǎn)的最短時(shí)間。

---

解題思路

首先我們考慮一個(gè)位置往一個(gè)方向發(fā)射第一個(gè)傳送門(mén)后如何移動(dòng)，最短的方法應(yīng)該是走到目前最近的一面墻開(kāi)第二個(gè)傳送門(mén)然后進(jìn)入。然后我們可以轉(zhuǎn)換一下模型

我們先預(yù)處理離每個(gè)點(diǎn)離最近的墻的距離

我們將原本的兩個(gè)傳送門(mén)變成直接瞬移到上下左右任意一睹墻面前，然后消耗代價(jià)為離最近的墻的距離。然后上下左右正常跑一遍$Spfa$即可。

為什么可以用$Spfa?$(他不是已經(jīng)死了嗎?)

證明:因?yàn)槊總€(gè)點(diǎn)連得邊到上下左右最遠(yuǎn)的墻，加上上下左右總共$8$條邊。所以不會(huì)有菊花圖

證畢

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define p(x,y) ((x-1)*m+y) using namespace std; const int N=510,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; struct node{int to,next,w; }a[N*N*20]; int n,m,s,t,f[N*N],ls[N*N],tot,mw[N][N]; int down[N][N],right[N][N],left[N][N],up[N][N]; char w[N][N]; bool v[N*N]; queue<int> q,p; void addl(int x,int y,int w) {a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot;} void bfs() {for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(w[i][j]=='#') q.push(i),p.push(j),mw[i][j]=0;while(!q.empty()){int x=q.front(),y=p.front();q.pop();p.pop();for(int k=0;k<4;k++){int zx=x+dx[k],zy=y+dy[k];if(zx<1||zy<1||zx>n||zy>m) continue;if(w[zx][zy]=='#'||v[p(zx,zy)]) continue;mw[zx][zy]=mw[x][y]+1;v[p(zx,zy)]=1;q.push(zx);p.push(zy);} }memset(v,0,sizeof(v)); } void spfa() {memset(f,0x3f,sizeof(f));q.push(s);v[s]=1;f[s]=0;while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(f[x]+a[i].w<f[y]){f[y]=f[x]+a[i].w;if(!v[y]){v[y]=1;q.push(y);}}}v[x]=0;} } int main() {//freopen("cell.in","r",stdin); // freopen("cell.out","w",stdout);scanf("%d%d\n",&n,&m);for(int i=1;i<=n;i++)gets(w[i]+1);memset(mw,0x3f,sizeof(mw));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){left[i][j]=left[i][j-1];up[i][j]=up[i-1][j];if(w[i][j]=='#') {left[i][j]=j,up[i][j]=i;}if(w[i][j]=='C') s=p(i,j);if(w[i][j]=='F') t=p(i,j);}for(int i=n;i>=1;i--)for(int j=m;j>=1;j--){right[i][j]=right[i][j+1];down[i][j]=down[i+1][j];if(w[i][j]=='#') {right[i][j]=j,down[i][j]=i;}}bfs();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){ if(w[i][j]=='#') continue;for(int k=0;k<2;k++){int zx=i+dx[k],zy=j+dy[k];if(w[zx][zy]=='#') continue;addl(p(i,j),p(zx,zy),1);addl(p(zx,zy),p(i,j),1);}if(left[i][j]+1!=j)addl(p(i,j),p(i,left[i][j]+1),mw[i][j]);if(up[i][j]+1!=i)addl(p(i,j),p(up[i][j]+1,j),mw[i][j]);if(right[i][j]-1!=j)addl(p(i,j),p(i,right[i][j]-1),mw[i][j]);if(down[i][j]-1!=i)addl(p(i,j),p(down[i][j]-1,j),mw[i][j]);}spfa();if(f[t]<=n*m) printf("%d",f[t]);else printf("nemoguce"); } /* 16 9 ######### ####.#### ####.#### ####.#### #.......# #...C...# #.......# #.......# #.......# #.......# #.......# #.......# ####.#### ####.#### ##F..#### ######### */

總結(jié)

以上是生活随笔為你收集整理的jzoj6286,P4442-走格子(Portal)【BFS,SPFA】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。