题解：P13173 [GCJ 2017 #2] Beaming With Joy
pipilong2024 · · 题解
妙妙题。
我是直接搜 2-SAT 搜到这题的，所以秒猜正解快人一步（
由于每个激光可以横纵随便调，所以输入的横纵方向没有任何作用，大可以直接将地图分为激光，墙，镜子（其实分两种镜子）三种点位。
注意到
2-SAT 直接存每个激光位横纵两种方式即可，下面考虑约束（即建边）。
考虑每个空地。
- 没有激光能射到它，无解。
- 有一个激光能射到它，那么该激光必须要放该方向。
- 有两个激光能射到它。
- 两个激光射到该空地的方向相同（即都是纵向射到空地或都是横向），无解，显然若要射到该空地必然会连锁射到另一个激光位。
- 两个激光射到该空地的方向不同，任选其一即可。
- 有三个激光能射到它。
- 三个激光射到该空地方向均相同，无解，理由同上。
- 只有两个激光射到该空地方向相同，一个不同，只能选那个不同的。
- 有
k 个激光能射到它。- 对于横纵两种方向，都有
\ge 2 个激光位，无解。 - 存在一种方向上只有
1 个激光位，则必须取该激光必须要放该方向。
- 对于横纵两种方向，都有
然后跑 2-SAT 求方案即可。
代码实现有点麻烦（也可能是我自己实现的麻烦）。 :::info[Code]
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define time ppldsg
const int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0}, t1[4] = {2, 3, 0, 1}, t2[4] = {3, 2, 1, 0};
const int maxn = 51, maxn_ = 5010;
int T, n, m;
int time, cnt, low[maxn_], dfn[maxn_], sccid[maxn_];
stack<int> st;
string mp[maxn];
vector<int> E[maxn_], path;
vector<pair<int, int>>e[maxn_];
void tarjan(int u) {
dfn[u] = low[u] = ++time;
st.push(u);
for (auto v : E[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (!sccid[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] != low[u]) return;
++cnt;
while (!st.empty()) {
int top = st.top();
st.pop();
sccid[top] = cnt;
if (top == u) break;
}
}
bool find(int x, int y, int dir) {
while (true) {
x += dx[dir], y += dy[dir];
if (x < 1 || x > n || y < 1 || y > m || mp[x][y] == '#') return 1;
else if (mp[x][y] == '|' || mp[x][y] == '-') return 0;
else if (mp[x][y] == '.') path.push_back(x * m + y - m);
else {
if (mp[x][y] == '\\') dir = t1[dir];
else dir = t2[dir];
}
}
}
void init() {
time = cnt = 0;
for (int i = 1; i <= n * m; i++) e[i].clear();
for (int i = 1; i <= n * m * 2; i++) sccid[i] = low[i] = dfn[i] = 0, E[i].clear();
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> T;
for (int _ = 1; _ <= T; _++) {
init();
cout << "Case #" << _ << ": ";
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> mp[i], mp[i] = "-" + mp[i];
#define getid(i,j) ((i-1)*m+j)
bool flag = 1;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
if (!flag) break;
if (mp[i][j] != '|' && mp[i][j] != '-') continue;
path.clear();
bool f1 = find(i, j, 0LL) && find(i, j, 1LL);
if (f1) for (int x : path) e[x].push_back({getid(i, j), 0});
else E[getid(i, j)].push_back(getid(i, j) + n * m);
path.clear();
bool f2 = find(i, j, 2LL) && find(i, j, 3LL);
if (f2) for (int x : path) e[x].push_back({getid(i, j), 1});
else E[getid(i, j) + n * m].push_back(getid(i, j));
if (!f1 && !f2) {
flag = 0;
break;
}
}
if (!flag) {
cout << "IMPOSSIBLE" << "\n";
continue;
}
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
if (!flag) break;
if (mp[i][j] != '.') continue;
int pos = getid(i, j);
if (e[pos].empty()) {
flag = 0;
break;
}
if (e[pos].size() == 1) {
int a = e[pos][0].first, b = e[pos][0].second;
E[a + !b * n * m].push_back(a + b * n * m);
} else {
int a = e[pos][0].first, b = e[pos][0].second, c = e[pos][1].first, d = e[pos][1].second;
E[a + !b * n * m].push_back(c + d * n * m), E[c + !d * n * m].push_back(a + b * n * m);
}
}
if (!flag) {
cout << "IMPOSSIBLE" << "\n";
continue;
}
for (int i = 1; i <= n * m * 2; i++) if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n * m; i++) if (sccid[i] == sccid[i + n * m]) {
flag = 0;
break;
}
if (!flag) {
cout << "IMPOSSIBLE" << "\n";
continue;
}
cout << "POSSIBLE" << "\n";
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (mp[i][j] == '|' || mp[i][j] == '-') cout << (sccid[i * m + j - m] > sccid[i * m + j - m + n * m] ? "|" : "-");
else cout << mp[i][j];
}
cout << "\n";
}
}
return 0;
}:::