没学过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; }转载于:https://www.cnblogs.com/LiM-817/p/10887160.html
