当前位置：首页 > news >正文

“金山-讯飞”杯2024年武汉理工大学程序设计竞赛 A. Mobiusp败走***（思维题-点双连通分量、连通性）

news 来源：原创 2024/9/20 5:47:12

题目

思路来源

官方题解

题解

手玩发现，能换的话，当且仅当.和1在一个环里，而这就是点双连通分量

所以最优策略是先把.换到(x,y)的位置，然后判断.和1在不在一个环里

也就是：

1. 判断删掉1时，.和(x,y)联通

2. 判断(x,y)和1在同一个连通分量里

这个和三者在同一个连通分量不等价，可以参考下图：

.和1并不在一个点双里，但是可以先把.换到(1,2)的位置里，使之在同一个点双里

3 3

1 2

#**
**1
.##

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=1500*1500+5,M=1500*1500*4+5,K=1502;
int n,m,u,v,ex,ey,blk,one,ed;
int low[N],dfn[N],tot,tp,cnt;
vector<P>stk;
bool vis[N];
char s[K][K];
vector<int>e[N];
int f(int x,int y){return x*m+y;
}
void add(int x,int y){e[x].pb(y);
}
bool dfs(int u,int fa){low[u]=dfn[u]=++tot;int ch=0;for(auto &v:e[u]){if(!dfn[v]){stk.pb(P(u,v));//记录当前BCC的边if(dfs(v,u))return 1;ch++;//从u这里向下dfs的子树的数量low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]){//割点ubool ok1=0,ok2=0;for(;;){P x=stk.back();stk.pop_back();int y=x.fi,z=x.se;ok1|=(y==one);ok2|=(y==ed);ok1|=(z==one);ok2|=(z==ed);//printf("one:%d ed:%d\n",y,z);if(ok1 && ok2)return 1;if(y==u && z==v)break;}}}else if(v!=fa && dfn[v]<dfn[u]){stk.pb(P(u,v));low[u]=min(low[u],dfn[v]);}}return 0;
}
bool dfs2(int u){vis[u]=1;if(u==blk)return 1;for(auto &v:e[u]){if(vis[v] || v==one)continue;if(dfs2(v))return 1;}return 0;
}
bool sol(){sci(n),sci(m);sci(ex);sci(ey);ex--;ey--;rep(i,0,n-1){scanf("%s",s[i]);}rep(i,0,n-1){rep(j,0,m-1){if(s[i][j]=='#')continue;int x=f(i,j);if(s[i][j]=='1')one=x;if(s[i][j]=='.')blk=x;if(i-1>=0 && s[i-1][j]!='#'){int y=f(i-1,j);//printf("x:%d y:%d\n",x,y);add(x,y);add(y,x);}if(j-1>=0 && s[i][j-1]!='#'){int y=f(i,j-1);//printf("x2:%d y2:%d\n",x,y);add(x,y);add(y,x);}}}ed=f(ex,ey);if(one==ed)return 1;if(!dfs2(ed))return 0;rep(i,0,n-1){rep(j,0,m-1){if(s[i][j]=='#')continue;int x=f(i,j);if(!dfn[x] && dfs(x,-1))return 1;}}return 0;
}
int main(){puts(sol()?"Yes":"No");return 0;
}