滑冰（Dev, Please Add This!）

FOI

2018-2019 XIX Open Cup, Grand Prix of Korea B

题解:
首先， $bfs$ 判断掉起点无法到达的情况。接下来只需要判断顺序。可以发现，任意一个点有上下经过和左右经过两种，且两种中至少有一个。于是一种非点连向另一种是点。同时我们发现，只有选择的点两者不联通（两点都不可到对方），才不存在方案。所以我们把不连通的点对强制不出现。用 $2-SAT$ 即可。
假设任意两点 $a,b$ 存在 $a->b$ 或 $b->a$ 或 $a<->b$ ，同时我们已经构造完 $1\sim n$，那么找到倒数第一个 $i->b$，同时可知 $b->((i+1)\sim n)$，于是我们修改路径为 $i->b->i+1$ 同样合法。若找不到，就以 $b$ 为起点或终点。充分性得证。
必要性显然。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,stx,sty,a[51][51];
inline int id(int x,int y){
	return (x-1)*m+y;
}
vector<int> in[5005],to[5005];
int bel1[51][51],bel2[51][51],lt,num[51][51],nt,dis[5005],vis[5005],f[5005][5005];
char s[51];
//# 0
//. 1
//o 2
//s 3
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int cal=0,sum=0;
inline int pd(int x,int y){
	return x>0&&x<=n&&y>0&&y<=m&&a[x][y]!=0;
}
void bfs(int x,int y){
	memset(dis,0,sizeof(dis));
	memset(vis,0,sizeof(vis));
	queue<int> q;
	q.push(bel1[x][y]);
	dis[bel1[x][y]]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=0;i<in[x].size();++i){
			vis[in[x][i]]=1;
		}
		for(int i=0;i<to[x].size();++i){
			int y=to[x][i];
			if(dis[y])continue;
			dis[y]=dis[x]+1;
			q.push(y);
		}
	}
	for(int i=1;i<=sum*2;++i){
		if(!vis[i])f[num[x][y]][i]=1;
	}
	memset(dis,0,sizeof(dis));
	memset(vis,0,sizeof(vis));
	q.push(bel2[x][y]);
	dis[bel2[x][y]]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=0;i<in[x].size();++i){
			vis[in[x][i]]=1;
		}
		for(int i=0;i<to[x].size();++i){
			int y=to[x][i];
			if(dis[y])continue;
			dis[y]=dis[x]+1;
			q.push(y);
		}
	}
	for(int i=1;i<=sum*2;++i){
		if(!vis[i])f[num[x][y]+sum][i]=1;
	}
}

int dfn[10005],low[10005],dfs_num,sta[10005],top,ins[10005];
vector<int> ed[10005];
inline void add(int x,int y){
	ed[x].push_back(y);
//	nex[++tot]=head[x];head[x]=tot;ver[tot]=y;
}
int cnt,cbl[80005];
void tarjan(int x){
	dfn[x]=low[x]=++dfs_num;
	sta[++top]=x;ins[x]=1;
	for(int i=0;i<ed[x].size();++i){
		int y=ed[x][i];
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}else if(ins[y]){
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(dfn[x]==low[x]){
		++cnt;
		int y;
		do{
			y=sta[top--],ins[y]=0;
			cbl[y]=cnt;
		}while(x!=y);
	}
}
inline void init(){
	memset(dfn,0,sizeof(dfn));
	for(int i=1;i<=nt;++i)for(int j=1;j<=nt;++j)f[i][j]=0;
	vector<int> tmp;
	for(int i=0;i<=lt;++i)in[i]=tmp,to[i]=tmp;
	for(int i=0;i<=nt*2;++i)ed[i]=tmp;
	nt=0;cnt=0;sum=0;cal=0;dfs_num=0;lt=0;
}
int main(){
	freopen("skate.in","r",stdin);
	freopen("skate.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		init();
		for(int i=1;i<=n;++i){
			scanf("%s",1+s);
			for(int j=1;j<=m;++j){
				if(s[j]=='#'){a[i][j]=0;++cal;}
				if(s[j]=='o'){a[i][j]=2;++sum;}
				if(s[j]=='S'){stx=i,sty=j;a[i][j]=3;++sum;}
				if(s[j]=='.')a[i][j]=1;
			}
		}
		int st=0;
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if(a[i][j]==2||a[i][j]==3)num[i][j]=++nt;
				if(a[i][j]==3)st=nt;
			}
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if((!pd(i,j-1))&&pd(i,j))++lt;
				if(pd(i,j))bel1[i][j]=lt;
				if(a[i][j]==2||a[i][j]==3){
					in[lt].push_back(num[i][j]);
				}
			}
		}
		for(int j=1;j<=m;++j){
			for(int i=1;i<=n;++i){
				if((!pd(i-1,j))&&pd(i,j))++lt;
				if(pd(i,j))bel2[i][j]=lt;
				if(a[i][j]==2||a[i][j]==3){
					in[lt].push_back(num[i][j]+sum);
				}
			}
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if((!pd(i,j-1))&&pd(i,j)){
					to[bel1[i][j]].push_back(bel2[i][j]);
				}else{
					if(pd(i,j)&&(!pd(i,j+1))){
						to[bel1[i][j]].push_back(bel2[i][j]);
					}
				}
			}
		}
		for(int j=1;j<=m;++j){
			for(int i=1;i<=n;++i){
				if((!pd(i-1,j))&&pd(i,j)){
					to[bel2[i][j]].push_back(bel1[i][j]);
				}else{
					if(pd(i,j)&&(!pd(i+1,j))){
						to[bel2[i][j]].push_back(bel1[i][j]);
					}
				}
			}
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if(a[i][j]==2||a[i][j]==3){
					bfs(i,j);
				}
			}
		}
		nt+=sum;
		for(int i=1;i<=nt;++i){
			for(int j=i+1;j<=nt;++j){
				if(f[i][j]&&f[j][i]){
					add(i,j+nt);add(j,i+nt);
				}
			}
		}
		for(int i=1;i<=sum;++i){
			add(i+nt,i+sum);
			add(i+sum+nt,i);
		}
		int fl=0;
		for(int i=0;i<4;++i){
			if(!pd(stx+dx[i],sty+dy[i]))fl=1;
		}
		if(!fl){
			add(st,st+sum+nt);add(st+sum,st+nt);
		}
		for(int i=1;i<=2*nt;++i){
			if(!dfn[i])tarjan(i);
		}
		int ans=1;
		for(int i=1;i<=nt;++i){
			if(cbl[i]==cbl[i+nt])ans=0;
		}
		for(int i=1;i<=sum;++i){
			if(f[st][i]&&f[st][i+sum]&&f[st+sum][i]&&f[st+sum][i+sum])ans=0;
		}
		if(ans)puts("Yes");
		else puts("No");
	}
	return 0;
}