没学过2-SAT... 亏爆
考虑把每个炮台当做一个01变量，0横着放，1竖着放，再把图转成约束条件。
具体来说：
如果某一种摆放方式能打到炮台：强制其为false, 即(addedge(true(x), false(x)))
某一个空地能被最多两个方向的炮台打到，就可以建立一个or关系。
就做完了（雾
输出方案就是2-SAT的经典问题了，不过代码中没写
#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;
}