430
spoj 208 Store-keeper bfs+重聯通分量
圖論書上的一道練習題，卻寫了整整一周。
思路很簡單，最簡單的想法是bfs+dfs，就是沒到拐點的時候dfs一次看是否可達，但是必然超時。所以就用重聯通分量優化。判斷拐點是否為割點，如果是割點，判斷兩邊是否在一個重聯通分量中。
一開始一直在考慮如何拐點是割點，兩邊的點也是不同重連通分量，但是這兩個重聯通分量並不是由拐點分割的怎麼處理，想到了用個鏈表記錄，然後二分判斷，但感覺複雜度太高，於是遲遲沒有動手敲。
後來才想明白因為兩邊的點必然與拐點有邊連接，所以如果不在同一聯通分量裏必然不可達。這樣判斷是否可達就可以O(1)處理了，不過我對於割點是每個開個vector，然後比較其中是否有相同的，感覺可以簡化
整體寫完後樣例都過不了，發現是bfs忘記記錄方向了，加了以後，WA，因為重聯通分量入棧位置出錯，改完WA，因為一個二維數組[][]寫成了[,],改完依舊WA，因為距離每次都取了最小值，這是錯誤的，改完繼續WA……因為初始化的時候，把一個賦值語句寫在了條件continue後麵，於是有的就沒賦值。
WA了n次，從POI官網上找到了數據，現在分享下（保存下麵的圖片，改成rar，第一個MAG文件夾）
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<stack>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
struct node
{
node(){}
node(int x,int y)
{
this->x=x;
this->y=y;
}
node(int d,int x,int y,int l)
{
this->x=x;
this->y=y;
this->last=l;
this->t=d;
}
bool operator !=(node &a) const
{
return a.x!=x||a.y!=y;
}
int x,y,last,t;
};
const int dir[4][2]={1,0,0,1,-1,0,0,-1};
int n,m;
node S,E,M;//start,end,man
stack<node> s;
queue<node> q;
int org[105][105];//記錄編號
bool Vis[105][105][4];//不同方向訪問
bool vis[105][105];
bool ok[105][105];//記錄初始位置可否到達
int low[105][105],dph[105][105];
int Key,cnt;
bool key[105][105];//記錄是否為割點
vector<int> K[105][105];
bool color[10005];
inline bool is_Case(int x,int y)
{
if(x<0||x>=n||y<0||y>=m||org[x][y]<0)return 1;
else return 0;
}
int dfs(int x,int y)
{
low[x][y]=dph[x][y]=cnt++;
vis[x][y]=1;
int tx,ty,t=0;
node now(x,y);
for(int i=0;i<4;i++)
{
tx=x+dir[i][0],ty=y+dir[i][1];
if(is_Case(tx,ty))continue;
s.push(now);//每次都需要加入當前節點，第一次錯誤就是在這
if(vis[tx][ty])//回邊
low[x][y]=min(low[x][y],dph[tx][ty]);
else
{
dfs(tx,ty);
if(low[tx][ty]>=dph[x][y])
{
key[x][y]=1;
K[x][y].push_back(Key);
while(s.top()!=now)
{
tx=s.top().x,ty=s.top().y;
if(!key[tx][ty]) org[tx][ty]=Key;
else K[tx][ty].push_back(Key);
s.pop();
}
t++;
Key++;
}
low[x][y]=min(low[x][y],low[tx][ty]);
}
}
if(x==S.x&&y==S.y&&t==1)//起點
{
key[x][y]=0;org[x][y]=Key-1;
}
}
int fold(int x,int y)//dfs
{
ok[x][y]=1;
for(int i=0,tx,ty;i<4;i++)
{
tx=x+dir[i][0];ty=y+dir[i][1];
if(is_Case(tx,ty)||ok[tx][ty])continue;
fold(tx,ty);
}
}
inline bool go(int i,node &a)//判斷拐點
{
if(i==a.last)return 1;
int tx=a.x-dir[a.last][0],ty=a.y-dir[a.last][1],nx=a.x-dir[i][0],ny=a.y-dir[i][1];
if(is_Case(nx,ny))return 0;
if(key[a.x][a.y])
{
if(key[nx][ny])swap(nx,tx),swap(ny,ty);
if(key[tx][ty])
{
int ok=0;
for(i=0;i<K[tx][ty].size();i++)//記錄割點所在連通分量
color[K[tx][ty][i]]=1;
if(key[nx][ny])
{
for(i=0;i<K[nx][ny].size();i++)
if(color[K[nx][ny][i]])
{ok=1;break;}
}
else if(color[org[nx][ny]])ok=1;
for(i=0;i<K[tx][ty].size();i++)//回複
color[K[tx][ty][i]]=0;
return ok;
}
else return org[tx][ty]==org[nx][ny];
}
else return 1;
}
int bfs(node a,node b)
{
while(!q.empty())q.pop();
memset(Vis,0,sizeof(Vis));
memset(color,0,sizeof(color));
int i,tx,ty;
for(i=0;i<4;i++)//加入四周節點
{
tx=a.x+dir[i][0];
ty=a.y+dir[i][1];
if(ok[tx][ty])
q.push(node(0,a.x,a.y,(i+2)%4));
}
while(!q.empty())
{
a=q.front();q.pop();
for(i=0;i<4;i++)
{
tx=a.x+dir[i][0];
ty=a.y+dir[i][1];
if(is_Case(tx,ty)||Vis[tx][ty][i]||!go(i,a))continue; //判斷是否可達
if(tx==b.x&&ty==b.y)break;
Vis[tx][ty][i]=1;
q.push(node(a.t+1,tx,ty,i));
}
if(tx==b.x&&ty==b.y)break;
}
return (tx==b.x&&ty==b.y)?a.t+1:0;
}
int main()
{
int T;
scanf("%d",&T);
while(T--&&~scanf("%d%d",&n,&m))
{
int i,j;
char c;
for(i=0;i<n;i++)
{
getchar();
for(j=0;j<m;j++)
{
K[i][j].clear(); //注意位置，不要再continue後麵
c=getchar();
if(c=='S')org[i][j]=-1;
else
{
org[i][j]=0;
if(c=='w')continue;
else if(c=='M')M.x=i,M.y=j;
else if(c=='P')S.x=i,S.y=j;
else E.x=i,E.y=j;
}
}
}
memset(ok,0,sizeof(ok));
int o=1;
org[S.x][S.y]=-1;
fold(M.x,M.y);//fill-flood判斷人能否到達箱子周圍
org[S.x][S.y]=0;
int tx,ty;
for(i=0;i<4;i++)//判斷能否到達周圍
{
tx=S.x+dir[i][0],ty=S.y+dir[i][1];
if(ok[tx][ty]) ok[S.x][S.y]=1;
}
if(ok[S.x][S.y])
{
while(!s.empty())s.pop();
Key=1;cnt=0;
memset(key,0,sizeof(key));
memset(vis,0,sizeof(vis));
dfs(S.x,S.y);//聯通分量標號
o=bfs(S,E); //bfs尋跡
}
else o=0;
if(o)printf("%d\n",o);
else puts("NO");
}
}
最後更新：2017-04-03 15:36:43