网站总体设计方案,免费发帖推广的平台,电子印章手机在线制作软件,织梦网站栏目题目 思路来源
官方题解 题解
手玩发现#xff0c;能换的话#xff0c;当且仅当.和1在一个环里#xff0c;而这就是点双连通分量
所以最优策略是先把.换到(x,y)的位置#xff0c;然后判断.和1在不在一个环里
也就是#xff1a;
1. 判断删掉1时#xff0c;.和(x,y)联…题目 思路来源
官方题解 题解
手玩发现能换的话当且仅当.和1在一个环里而这就是点双连通分量
所以最优策略是先把.换到(x,y)的位置然后判断.和1在不在一个环里
也就是
1. 判断删掉1时.和(x,y)联通
2. 判断(x,y)和1在同一个连通分量里 这个和三者在同一个连通分量不等价可以参考下图
.和1并不在一个点双里但是可以先把.换到(1,2)的位置里使之在同一个点双里 3 3 1 2 #** **1 .## 代码
#includebits/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 pairint,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#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 N1500*15005,M1500*1500*45,K1502;
int n,m,u,v,ex,ey,blk,one,ed;
int low[N],dfn[N],tot,tp,cnt;
vectorPstk;
bool vis[N];
char s[K][K];
vectorinte[N];
int f(int x,int y){return x*my;
}
void add(int x,int y){e[x].pb(y);
}
bool dfs(int u,int fa){low[u]dfn[u]tot;int ch0;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 ok10,ok20;for(;;){P xstk.back();stk.pop_back();int yx.fi,zx.se;ok1|(yone);ok2|(yed);ok1|(zone);ok2|(zed);//printf(one:%d ed:%d\n,y,z);if(ok1 ok2)return 1;if(yu zv)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(ublk)return 1;for(auto v:e[u]){if(vis[v] || vone)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 xf(i,j);if(s[i][j]1)onex;if(s[i][j].)blkx;if(i-10 s[i-1][j]!#){int yf(i-1,j);//printf(x:%d y:%d\n,x,y);add(x,y);add(y,x);}if(j-10 s[i][j-1]!#){int yf(i,j-1);//printf(x2:%d y2:%d\n,x,y);add(x,y);add(y,x);}}}edf(ex,ey);if(oneed)return 1;if(!dfs2(ed))return 0;rep(i,0,n-1){rep(j,0,m-1){if(s[i][j]#)continue;int xf(i,j);if(!dfn[x] dfs(x,-1))return 1;}}return 0;
}
int main(){puts(sol()?Yes:No);return 0;
}
