图论书上的一道练习题，却写了整整一周。
思路很简单，最简单的想法是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");
}
}
时间： 2024-07-28 18:26:43