没学过2-SAT... 亏爆

考虑把每个炮台当做一个01变量，0横着放，1竖着放，再把图转成约束条件。

具体来说：

如果某一种摆放方式能打到炮台：强制其为false, 即\(addedge(true(x), false(x))\)

某一个空地能被最多两个方向的炮台打到，就可以建立一个or关系。

就做完了（雾

输出方案就是2-SAT的经典问题了，不过代码中没写

#include 
    
     #define mp make_pair#define fi first#define se secondusing namespace std;const int lim = 10000 + 10;const int N = 100 + 5;int T, n, m;vector 
     
       G[lim];char c[N][N];int cov[2][N][N], fix[N][N], scc, instack[lim] , color[lim];vector 
      
        v[N][N];int low[lim], dfn[lim];pair 
       
         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 
        
          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 
         
           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 <
          
            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;}