没学过2-SAT… 亏爆
考虑把每个炮台当做一个01变量，0横着放，1竖着放，再把图转成约束条件。
具体来说：
如果某一种摆放方式能打到炮台：强制其为false, 即$addedge(true(x), false(x))$
某一个空地能被最多两个方向的炮台打到，就可以建立一个or关系。
就做完了（雾
输出方案就是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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int lim = 10000 + 10;
const int N = 100 + 5;
int T, n, m;
vector <int> G[lim];
char c[N][N];
int cov[2][N][N], fix[N][N], scc, instack[lim] , color[lim];
vector <int> v[N][N];
int low[lim], dfn[lim];
pair <int , int> change(int x, int y) {
swap(x, y);
if(x != 0) x = -x; if(y != 0) y = -y;
return make_pair(x, y);
}
bool dfs(int x, int y, int dx, int dy, int id) {
//cout << x << " " << y << " " << dx << " " << dy << " " << id << endl;
if(x < 1 || x > n || y < 1 || y > m || c[x][y] == '#') return 1;
if(c[x][y] == '-' || c[x][y] == '|') return 0;
cov[id][x][y] = 1;
if(c[x][y] == '/') {
pair <int, int> nxt = change(dx, dy);
return dfs(x + nxt.fi, y + nxt.se, nxt.fi, nxt.se, id);
}
else if(c[x][y] == '\\')
return dfs(x + dy, y + dx, dy, dx, id);
else if(c[x][y] == '.') return dfs(x + dx, y + dy, dx, dy, id);
}
stack <int> s;
int dfs_clock;
void tarjan(int u) {
low[u] = dfn[u] = ++dfs_clock;
s.push(u); instack[u] = 1;
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if(instack[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
++scc;
while(1) {
int t = s.top(); s.pop(); instack[t] = 0;
color[t] = scc;
if(t == u) break;
}
}
}
void solve() {
while(!s.empty()) s.pop();
scanf("%d%d", &n, &m);
for(int i = 1; i <= 10000; i++) G[i].clear();
for(int i = 1; i <= n; i++) scanf("%s", (c[i] + 1));
int cnt = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
fix[i][j] = 0, v[i][j].clear();
memset(low, 0, sizeof(low));
memset(dfn, 0, sizeof(dfn));
memset(color, 0, sizeof(color));
scc = 0; dfs_clock = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
if(c[i][j] == '-' || c[i][j] == '|') {
cnt++;
memset(cov, 0, sizeof(cov));
// number : cnt , cnt ^ 1
//cout << "now dfs:" << i <<" " << j <<endl;
int id1 = dfs(i, j-1, 0, -1, 0), id2 = dfs(i, j+1, 0, 1, 0);
int id3 = dfs(i-1, j, -1, 0, 1) , id4 = dfs(i+1, j, 1, 0, 1);
int num0 = (id1 && id2);
int num1 = (id3 && id4);
if(!num0 && !num1) { // 都会攻击到别人
puts("IMPOSSIBLE");
//cout << i << " " << j << endl;
return ;
}
// 2 sat 中强制x为false: (~x | ~x)
// x = true -> x = false
else if(!num0) {
for(int k = 1; k <= n; k++)
for(int l = 1; l <= m; l++) {
if(cov[1][k][l] == 1 && c[k][l] == '.') v[k][l].push_back(cnt<<1|1);
}
G[cnt<<1].push_back(cnt<<1|1);
}
else if(!num1) {
for(int k = 1; k <= n; k++)
for(int l = 1; l <= m; l++)
if(cov[0][k][l] == 1 && c[k][l] == '.') v[k][l].push_back(cnt<<1);
G[cnt<<1|1].push_back(cnt<<1);
}
else {
for(int k = 1; k <= n; k++) {
for(int l = 1; l <= m; l++) if(c[k][l] == '.'){
if(cov[0][k][l] && cov[1][k][l]) fix[k][l] = 1;
else if(cov[0][k][l]) v[k][l].push_back(cnt<<1);
else if(cov[1][k][l]) v[k][l].push_back(cnt<<1|1);
}
}
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) if(c[i][j] == '.' && fix[i][j] != 1){
if(v[i][j].size() == 0) {
puts("IMPOSSIBLE");
return ;
}
else if(v[i][j].size() == 1) {
G[v[i][j][0]^1].push_back(v[i][j][0]);
}
else if(v[i][j].size() == 2) {
// 经典的u or v
int uu = v[i][j][0], vv = v[i][j][1];
G[uu^1].push_back(vv); G[vv^1].push_back(uu);
}
}
}
for(int i = 2; i <= (cnt << 1 | 1); i++) if(!dfn[i]) tarjan(i);
for(int i = 1; i <= (cnt); i++) if(color[i<<1] == color[i<<1|1]) {
puts("IMPOSSIBLE");
return ;
}
puts("POSSIBLE");
}
int main() {
scanf("%d", &T);
while(T--) solve();
return 0;
}