code


#include <bits/stdc++.h>
#define ok printf ("ok on line#%d\n", __LINE__)
#define ll long long
using namespace std;
template <typename T>
void read(T &x) {
	x = 0; char c = getchar(); int f = 0;
	for (; !isdigit(c); c = getchar())
		f |= c == '-';
	for (; isdigit(c);  c = getchar())
		x = x * 10 + (c ^ '0');
	if (f) x = -x;
}

template <typename T>
void write(T x, char ed = '\n') {
	if (x < 0) putchar('-'), x = -x;
	static short st[30], tp;
	do st[++tp] = x % 10, x /= 10; while (x);
	while (tp) putchar(st[tp--] | '0');
	putchar(ed);
}

const int M = 10000005, N = 95333;
int id[55][55], fr[M], dfn[N], low[N], stx[N], sty[N], ne[M], to[M], h[N], tot, ttp, tp;
int v[2555][2555], ed[2555][2555], vis[N], st[N], col[N], a[55][55], ncnt, cnt, T, sx, sy, sc, m, n;
char s[55];
template <typename T>
void Mn(T &x, T y) { if (x > y) x = y; }
inline void adde(int x, int y) { 
	//printf ("adde(%d, %d)\n", x, y);
	ne[++tot] = h[x], to[h[x] = tot] = y, fr[tot] = x;
}
void dfs(int x, int *tag) {
	tag[x] = 1;
	for (int i = h[x]; i; i = ne[i]) 
		if (!tag[to[i]]) dfs(to[i], tag);
}
void tarjan(int x) {
	low[x] = dfn[x] = ++cnt;
	st[++ttp] = x, vis[x] = 1;
	for (int i = h[x]; i; i = ne[i]) {
		int y = to[i];
		if (!dfn[y]) tarjan(y), Mn(low[x], low[y]);
		else if (vis[y]) Mn(low[x], dfn[y]);
	}
	if (dfn[x] == low[x]) {
		int z; ++sc;
		while (z = st[ttp--]) {
			col[z] = sc, vis[z] = 0;
			if (z == x) break;
		}
	}
}

int main() {
	freopen ("skate.in","r",stdin);
	freopen ("skate.out","w",stdout);
	for (read(T); T; T--) {
		read(n), read(m), memset(a, 0, sizeof(a));
		memset(h, 0, sizeof(h)), tot = ncnt = tp = 0;
		memset(id, 0, sizeof(id));
		for (int i = 0;i <= n + 1; ++i) a[i][0] = a[i][m + 1] = 1;
		for (int i = 0;i <= m + 1; ++i) a[0][i] = a[n + 1][i] = 1;
		for (int i = 1;i <= n; ++i) {
			scanf ("%s", s + 1);
			for (int j = 1;j <= m; ++j) {
				a[i][j] = s[j] == '#'; 
				if (s[j] == 'o') stx[++tp] = i, sty[tp] = j;
				else if (s[j] == 'S') sx = i, sy = j;
			}
		}
		for (int i = 1;i <= n; ++i) 
			for (int j = 1;j <= m; ++j) if (!a[i][j]) {
				if (a[i-1][j] || a[i+1][j] || a[i][j-1] || a[i][j+1]) id[i][j] = ++ncnt;
				else if (sx == i || sy == j) id[i][j] = ++ncnt;
			}
		for (int i = 1;i <= n; ++i) {
			for (int j = 1;j <= m; ++j) if (id[i][j]) {
				int t = j;
				while (!a[i][t - 1]) --t;
				if (t != j) adde(id[i][j], id[i][t]);
				t = j;
				while (!a[i][t + 1]) ++t;
				if (t != j) adde(id[i][j], id[i][t]);
				t = i;
				while (!a[t - 1][j]) --t;
				if (t != i) adde(id[i][j], id[t][j]);
				t = i;
				while (!a[t + 1][j]) ++t;
				if (t != i) adde(id[i][j], id[t][j]);
			}
		}
		memset(dfn, 0, sizeof(dfn)), cnt = sc = 0;
		for (int i = 1;i <= ncnt; ++i)
				if (!dfn[i]) tarjan(i);
		int tmp = tot; tot = 0; memset(h, 0, sizeof(h));
		memset(ed, 0, sizeof(ed));
		for (int i = 1;i <= sc; ++i) ed[i][i] = 1;
		for (int i = 1;i <= tmp; ++i) {
			int x = col[fr[i]], y = col[to[i]];
			if (!ed[x][y]) adde(x, y), ed[x][y] = 1;
		}
		memset(v, 0, sizeof(v));
		for (int i = 1;i <= sc; ++i) dfs(i, v[i]);
		memset(h, 0, sizeof(h)), tot = 0;
		int rt = col[id[sx][sy]];
		for (int i = 1;i <= sc; ++i) {
			if (!v[rt][i]) adde(i, i + sc);
			for (int j = 1;j <= sc; ++j)
				if (!v[i][j] && !v[j][i]) adde(i, j + sc), adde(j, i + sc);
		}
		for (int i = 1;i <= tp; ++i) {
			int x = stx[i], y = sty[i], t = x;
			while (!a[t - 1][y]) --t;
			int t1 = col[id[t][y]];
			t = y;
			while (!a[x][t - 1]) --t;
			int t2 = col[id[x][t]];
			adde(t1 + sc, t2), adde(t2 + sc, t1);
		}
		memset(dfn, 0, sizeof(dfn)), cnt = 0;
		int t = sc; sc = 0;
		for (int i = 1;i <= 2 * t; ++i)
			if (!dfn[i]) tarjan(i);
		int fl = 1;
		for (int i = 1;i <= t; ++i)
			if (col[i] == col[i + t]) fl = 0;
		puts(fl ? "Yes" : "No");
	}
	return 0;
}

上一篇:tp实现日志的写入


下一篇:dik