題干：

有一個倉庫被分成n*m?個矩形區域，如果兩個區域有一條公共邊，則被認為這兩個區域相鄰。包裹都放在一個區域中，剩余的區域或者空閑或者被集裝箱占有，這是因為集裝箱太重，倉庫管理員不能將集裝箱搬走。倉庫管理員目是是要將包裹從開始的P區域移動到最后的K區域。他可以從空區域走到與之相鄰的一個空區域。當倉庫管理員走到與包裹相鄰的區域時，它可以推動包裹，具體的推動方法如下所示：

?讀入一個儲藏表，開始位置為倉庫管理員，最后位置為包裹移動的位置

Input

S –?集裝箱,

M –倉庫管理員的位置,

P –包裹開始的位置,

K –包裹最后的位置,

w –空區域.?

S, M, P?和?K?在文件中只出現一次.

第一行有兩個用單個空格分隔的正整數n,m<=100.?接下來是貨物存放二維表.共N行，每行為M?個字母組成的單詞，字母分別是S, M, P, K, w.?第i單詞的第j個位置表示第i行第j列區域的信息，可能是如下內容:?

Output

如果包裹不能移動到目的位置，則寫入NO。

如果包裹能移動到目的位置，則寫入最小的移動次數。

Sample Input

10 12

SSSSSSSSSSSS

SwwwwwwwSSSS

SwSSSSwwSSSS

SwSSSSwwSKSS

SwSSSSwwSwSS

SwwwwwPwwwww

SSSSSSSwSwSw

SSSSSSMwSwww

SSSSSSSSSSSS

SSSSSSSSSSSS

Sample Output

7

題目大意：

?中文題意。

解題報告：

這道題描述的是我們玩過的經典的小游戲，推箱子。由于要求步數最少，基本的想法是BFS，記錄人的位置和箱子的位置兩個狀態。但是狀態數過多，有100*100*100*100，進一步思考可以發現記錄人的絕對位置是沒有必要的，因為只有人在箱子旁邊的單元格內，才能推箱子，所以只需記錄箱子的位置和人在箱子的方向，只有100100*4個狀態。
考慮bfs出所有可以到達的狀態，O(1)回答詢問。?
用f[x][y][i]表示箱子在(x,y)，人在箱子的i方向。（人不在箱子旁時沒啥用，所以可以壓縮狀態）?
兩種轉移：（一般來講先動箱子再換人的方向）
1、推箱子，很好轉移。?
2、箱子不動，人換方向。?

因為題目意思是：只有箱子動了一步，才算是移動次數+1.而人的移動不算移動次數，也就是說只需要考慮兩點是否存在不經過箱子的路徑，而不需要考慮最短路徑是多少。

一個題解：

可以預處理出所有的點雙來快速判斷。因為這兩點一定至少連通，所以如果兩點都在一個點雙里就可以。否則一定不可以。?
怎么判斷兩點是否同在一個點雙中呢qaq，就是圓方樹上這兩點距離為2即可。不過好像內存開不下，時間多個log也吃不消。我們發現其實隨便記一下父親就可以O(1)了qaq。?
復雜度O(nm)

另一個題解：

進一步思考，發現兩地如果連通，必須至少存在一條路徑，如果總是連通，必須至少存在兩條路徑。也就是說，無論箱子作為障礙擋在哪條路徑上，總還有另一條路徑使這兩點連通。這恰好是圖論中雙連通分支(點雙連通)的定義，即沒有割點的連通分支。所以可以這樣判斷，對于一個連通圖，如果箱子不在割點上，箱子旁邊的兩點(人的位置)一定連通，如果箱子在割點上，則人的兩點位置是否連通，取決于兩點是否同屬一個雙連通分支。于是我們可以預處理出圖中的所有割點和雙連通分支，然后每次判斷兩點連通只需O(1)的時間。這樣就可以解決這道題了。

AC代碼：（因為沒法交不上題所以貼一個網上的代碼過來鏈接）（但是好像注釋的那幾行，用沒注釋的那個就可以過，用了就過不了）

#include <bits/stdc++.h> using namespace std; #define ll long long #define inf 0x3f3f3f3f #define N 110 inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f; } int n,m,Q,id[N][N],h[N*N],num=0,f[N][N][4],owo=0,sx,sy,bx,by,tx,ty; int dx[]= {0,-1,1,0},dy[]= {-1,0,0,1}; //0--往左推,1--上,2--下,3--右 char s[N];bool vis[N][N]; int dfn[N*N],low[N*N],dfnum=0,bel[N*N],ofo=0,fa[N*N]; bool isge[N*N]; struct edge {int to,next; } data[N*N*4]; struct Icefox {int x,y,op;Icefox(int _x,int _y,int _op=0) {x=_x;y=_y;op=_op;} }; inline void add(int x,int y){data[++num].to=y;data[num].next=h[x];h[x]=num;data[++num].to=x;data[num].next=h[y];h[y]=num; } stack<int>qq; inline void tarjan(int x,int Fa) {dfn[x]=low[x]=++dfnum;qq.push(x);for(int i=h[x]; i; i=data[i].next) {int y=data[i].to;if(y==Fa) continue;if(!dfn[y]) {tarjan(y,x);low[x]=min(low[x],low[y]);if(low[y]<dfn[x]) continue;++ofo;fa[ofo]=x;isge[x]=1;while(1) {int z=qq.top();qq.pop();bel[z]=ofo;if(z==y) break;}continue;} low[x]=min(low[x],dfn[y]);} } inline bool jud(int x,int y,int z) {return bel[x]==bel[y]||fa[bel[x]]==y||fa[bel[y]]==x;//用下面那兩行就過不了，不知道為什么 // if(isge[z]==1) return bel[x]==bel[y]; // else return 1; } int main() {n=read();m=read();for(int i=1; i<=n; ++i) {scanf("%s",s+1);for(int j=1; j<=m; ++j) {if(s[j]=='S') continue;id[i][j]=++owo;if(s[j]=='M') sx=i,sy=j;if(s[j]=='P') bx=i,by=j;if(s[j]=='K') tx=i,ty=j;for(int k=0; k<2; ++k) {int x=i+dx[k],y=j+dy[k];if(x<1||x>n||y<1||y>m||!id[x][y]) continue;add(id[i][j],id[x][y]);//直接就是加雙向邊 }}}for(int i=1; i<=owo; ++i) if(!dfn[i]) tarjan(i,0);memset(f,-1,sizeof(f));queue<Icefox>q;q.push(Icefox(sx,sy));vis[sx][sy]=1;while(!q.empty()) {int x=q.front().x,y=q.front().y;q.pop();for(int i=0; i<4; ++i) {int xx=x+dx[i],yy=y+dy[i];if(xx<1||xx>n||yy<1||yy>m||!id[xx][yy]) continue;if(vis[xx][yy]||xx==bx&&yy==by) continue;vis[xx][yy]=1;q.push(Icefox(xx,yy));}}for(int i=0; i<4; ++i) {int x=bx+dx[i],y=by+dy[i];if(x<1||x>n||y<1||y>m||!vis[x][y]) continue;f[bx][by][i]=0;q.push(Icefox(bx,by,i));}while(!q.empty()) {int x=q.front().x,y=q.front().y,op=q.front().op;q.pop();if(x==tx&&y==ty) {printf("%d\n",f[x][y][op]);return 0;}int xx=x+dx[3-op],yy=y+dy[3-op];//移動箱子到(xx,yy) if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&id[xx][yy]&&f[xx][yy][op]==-1)f[xx][yy][op]=f[x][y][op]+1,q.push(Icefox(xx,yy,op));for(int i=0; i<4; ++i) {//移動人到另一個方向 if(f[x][y][i]!=-1) continue;xx=x+dx[i];yy=y+dy[i];if(!id[xx][yy]) continue;if(!jud(id[xx][yy],id[x+dx[op]][y+dy[op]],id[x][y])) continue;f[x][y][i]=f[x][y][op];q.push(Icefox(x,y,i));}}puts("NO");return 0; }

改了一下，判斷兩點是否有第二個路徑的時候，是這樣判斷的：已知人移動前的位置編號x，人移動后的位置編號y，箱子所在位置編號z，因為一個事實的存在：xyz三點一定是相鄰的，并且z被夾在中間，也就是不會有x-y-z這種情況，那么看xy是否連通，可以分z的兩種情況考慮：z如果是割點，那xy必須要屬于一個bcc才return1；如果z不是割點，那么直接return 1就行（其實還是在一個bcc中），因為這時候要么xy都不是割點，也就是都屬于一個bcc中（因為相鄰的三個點都不是割點那么一定屬于同一個bcc），要么x或者y其中一個是割點，此時割點也可以看成和z是在一個bcc中的，所以也可以歸類上去。當然，似乎還有種特殊情況，就是一共就三個點，這時這三個點屬于兩個bcc，但是這種情況的話z一定是割點，屬于我們分類的第一種情況而不是現在討論的第二種，所以在第二種情況中不需要考慮。

代碼如下：（不知道正確與否）

#include <bits/stdc++.h> using namespace std; #define ll long long #define inf 0x3f3f3f3f #define N 110 inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f; } int n,m,Q,id[N][N],h[N*N],num=0,f[N][N][4],owo=0,sx,sy,bx,by,tx,ty; int dx[]= {0,-1,1,0},dy[]= {-1,0,0,1}; //0--往左推,1--上,2--下,3--右 char s[N]; bool vis[N][N]; int dfn[N*N],low[N*N],dfnum=0,bel[N*N],ofo=0,fa[N*N]; bool isge[N*N]; struct edge {int to,next; } data[N*N*4]; struct Icefox {int x,y,op;Icefox(int _x,int _y,int _op=0) {x=_x;y=_y;op=_op;} }; inline void add(int x,int y) {data[++num].to=y;data[num].next=h[x];h[x]=num;data[++num].to=x;data[num].next=h[y];h[y]=num; } stack<int>qq; inline void tarjan(int x,int Fa) {dfn[x]=low[x]=++dfnum;qq.push(x);for(int i=h[x]; i; i=data[i].next) {int y=data[i].to;if(y==Fa) continue;if(!dfn[y]) {tarjan(y,x);low[x]=min(low[x],low[y]);if(low[y]<dfn[x]) continue;++ofo;fa[ofo]=x;isge[x]=1;while(1) {int z=qq.top();qq.pop();bel[z]=ofo;if(z==y) break;}continue;}low[x]=min(low[x],dfn[y]);} } inline bool jud(int x,int y,int z) {if(isge[z]==1) return bel[x]==bel[y];else return 1; } int main() {n=read();m=read();for(int i=1; i<=n; ++i) {scanf("%s",s+1);for(int j=1; j<=m; ++j) {if(s[j]=='S') continue;id[i][j]=++owo;if(s[j]=='M') sx=i,sy=j;if(s[j]=='P') bx=i,by=j;if(s[j]=='K') tx=i,ty=j;for(int k=0; k<2; ++k) {int x=i+dx[k],y=j+dy[k];if(x<1||x>n||y<1||y>m||!id[x][y]) continue;add(id[i][j],id[x][y]);//直接就是加雙向邊 }}}for(int i=1; i<=owo; ++i) if(!dfn[i]) tarjan(i,0);memset(f,-1,sizeof(f));queue<Icefox>q;q.push(Icefox(sx,sy));vis[sx][sy]=1;while(!q.empty()) {int x=q.front().x,y=q.front().y;q.pop();for(int i=0; i<4; ++i) {int xx=x+dx[i],yy=y+dy[i];if(xx<1||xx>n||yy<1||yy>m||!id[xx][yy]) continue;if(vis[xx][yy]||xx==bx&&yy==by) continue;vis[xx][yy]=1;q.push(Icefox(xx,yy));}}for(int i=0; i<4; ++i) {int x=bx+dx[i],y=by+dy[i];if(x<1||x>n||y<1||y>m||!vis[x][y]) continue;f[bx][by][i]=0;q.push(Icefox(bx,by,i));}while(!q.empty()) {int x=q.front().x,y=q.front().y,op=q.front().op;q.pop();if(x==tx&&y==ty) {printf("%d\n",f[x][y][op]);return 0;}int xx=x+dx[3-op],yy=y+dy[3-op];//移動箱子到(xx,yy) if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&id[xx][yy]&&f[xx][yy][op]==-1)f[xx][yy][op]=f[x][y][op]+1,q.push(Icefox(xx,yy,op));for(int i=0; i<4; ++i) {//移動人到另一個方向 if(f[x][y][i]!=-1) continue;xx=x+dx[i];yy=y+dy[i];if(!id[xx][yy]) continue;if(!jud(id[xx][yy],id[x+dx[op]][y+dy[op]],id[x][y])) continue;f[x][y][i]=f[x][y][op];q.push(Icefox(x,y,i));}}puts("NO");return 0; }

?

總結

以上是生活随笔為你收集整理的【BZOJ - 2574】[Poi1999] Store-Keeper（点双连通分量，求割点，记忆化bfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。