GYM102959B Dev,Please Add This! 题解

First Post:

Last Update:

做的时候感觉到了一个星星只会被两种方式覆盖，但因为卡在最后一个小小的正确性问题上导致没做出来。这篇文章尽量把正确性说得详细点。

如果直接硬做这个题，会发现其类似一个哈密顿路问题，根本做不得。故考虑发现性质。考虑一个星星左边和右边最靠近它的围墙，分别设为 。加入我们横着经过了这个星星，那么要么停在 右边的第一个位置，要么停在 左边的第一个位置。既然如此，我们干脆把 右边到 左边的点都走一遍，这不会影响之后的走法，且不劣。于是横着经过这个星星的方法全都可以被看作一种，即直接经过 右边与 左边的所有格子。

也就是说，每个星星只有两种被经过的方式，每种方式在网格图上体现为一条线段。

我们把这些线段提出来，在网格图上游走的方式就等价于选出一个线段的集合 ，使得我们可以到达 中的所有线段。考察两条线段之间的关系，如果线段 不能到达线段 ，那么 和 肯定有一个不在 中。如果起始点无法到达线段 ，那线段 肯定不在 中。对于经过一个星星的两条线段 ， 和 必须有一个在 中。

对线段 定义布尔变量 ，那么上述限制就是一个 2-SAT 问题，直接用 tarjan 算法求解即可。

还有一个问题：为何“ ， 能到达 或 能到达 ”和 “存在一种方式经过 中的所有线段

“ 是等价的？必要性显然，充分性还需证明。

考虑依次遍历 中的线段 ，将 加入已有的路径 中。找到 中最后一个满足 能到达 的线段 ，那么 能到达原来在 后面的那条线段（因为我们保证了任意两条线段至少有一条能到达另一条），所以把 直接放在 后面即可。如果 后没有线段或找不到这样的 ，直接把 插到结尾或开头即可。

于是本题就做完了。时间复杂度为 。这实际上是 2-SAT 的限制个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
const int N = 55,V = 1e4 + 5,M = 2e7 + 5;
typedef pair<int,int> pii;
#define FI first
#define SE second
int n,m;
char s[N][N];
int tot;
namespace TwoSAT {
	int fir[V],nxt[M],to[M],ect = 1;
	inline void addedge(int u1,int v1) {
		nxt[++ect] = fir[u1];fir[u1] = ect;to[ect] = v1;
	}
	inline void ins(int u1,int v1) {
		addedge(u1,v1);
		u1 = u1 > tot ? u1 - tot : u1 + tot;
		v1 = v1 > tot ? v1 - tot : v1 + tot;
		// addedge(v1,u1);
	}
	int dfn[V],low[V],co[V],stk[V],top,col;
	void tarjan(int x) {
		dfn[x] = low[x] = ++dfn[0];
		stk[++top] = x;
		for(int i = fir[x],y;y = to[i],i;i = nxt[i]) {
			if(!dfn[y])
				tarjan(y),low[x] = min(low[x],low[y]);
			else if(!co[y]) low[x] = min(low[x],dfn[y]);
		}
		if(low[x] == dfn[x]) {
			co[x] = ++col;
			while(stk[top] != x)
				co[stk[top]] = col,--top;
			--top;
		}
	}
	inline bool Check() {
		for(int i = 1;i <= tot + tot;i++) if(!dfn[i]) tarjan(i);
		for(int i = 1;i <= tot;i++)
			if(co[i] == co[i + tot]) return 0;
		return 1;
	}
}
int Idh[N][N],Idv[N][N]; // 横线和竖线的标号
pii st[V],ed[V];
bitset<V> can[V];
void dfs(int id,int x) {
	can[id].set(x);
	int y = x ^ Idh[st[x].FI][st[x].SE] ^ Idv[st[x].FI][st[x].SE]; // 两个 Id 总有一个为 x，这样方便得到另一个 Id
	if(!can[id][y]) dfs(id,y);
	y = x ^ Idh[ed[x].FI][ed[x].SE] ^ Idv[ed[x].FI][ed[x].SE];
	if(!can[id][y]) dfs(id,y);
}
int main() {
	cin >> n >> m;
	int stx = 0,sty = 0;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++) {
			cin >> s[i][j];
			if(s[i][j] == 'O') stx = i,sty = j;
		}
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++) if(s[i][j] != '#') {
			if(j == 1 || s[i][j - 1] == '#') st[++tot] = make_pair(i,j);
			Idh[i][j] = tot;
			if(j == m || s[i][j + 1] == '#') ed[tot] = make_pair(i,j);
		}
	for(int j = 1;j <= m;j++)
		for(int i = 1;i <= n;i++) if(s[i][j] != '#') {
			if(i == 1 || s[i - 1][j] == '#') st[++tot] = make_pair(i,j);
			Idv[i][j] = tot;
			if(i == n || s[i + 1][j] == '#') ed[tot] = make_pair(i,j);
		}
	for(int i = 1;i <= tot;i++) dfs(i,i);
	for(int i = 1;i <= tot;i++)
		if(!can[Idh[stx][sty]][i] && !can[Idv[stx][sty]][i])
			TwoSAT::ins(i,i + tot);
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			if(s[i][j] == '*')
				TwoSAT::ins(Idh[i][j] + tot,Idv[i][j]),
				TwoSAT::ins(Idv[i][j] + tot,Idh[i][j]);
	for(int i = 1;i <= tot;i++)
		for(int j = i + 1;j <= tot;j++)
			if(!can[i][j] && !can[j][i])
				TwoSAT::ins(i,j + tot),TwoSAT::ins(j,i + tot);
	if(TwoSAT::Check()) puts("YES");
	else puts("NO");
	return 0;
}
≡