显示原始代码
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m))
return 0;
int N = n * m;
vector<int> init_mask(N);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> init_mask[i * m + j];
}
}
vector<vector<int>> D(N);
auto is_straight = [&](int x) { return x == 5 || x == 10; };
for (int id = 0; id < N; id++) {
int mask = init_mask[id];
int deg = __builtin_popcount(mask);
if (deg != 2) {
D[id] = { mask };
} else {
if (is_straight(mask)) {
D[id] = { 5, 10 };
} else {
D[id] = { 3, 6, 12, 9 };
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int id = i * m + j;
auto &v = D[id];
vector<int> tmp;
for (int mask : v) {
if (i == 0 && (mask & 1))
continue;
if (j == m - 1 && (mask & 2))
continue;
if (i == n - 1 && (mask & 4))
continue;
if (j == 0 && (mask & 8))
continue;
tmp.push_back(mask);
}
v.swap(tmp);
if (v.empty()) {
cout << -1;
return 0;
}
}
}
vector<vector<pair<int, int>>> adj(N);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int id = i * m + j;
if (i > 0) {
adj[id].emplace_back((i - 1) * m + j, 0);
}
if (j < m - 1) {
adj[id].emplace_back(i * m + (j + 1), 1);
}
if (i < n - 1) {
adj[id].emplace_back((i + 1) * m + j, 2);
}
if (j > 0) {
adj[id].emplace_back(i * m + (j - 1), 3);
}
}
}
deque<pair<int, int>> que;
for (int u = 0; u < N; u++) {
for (auto &pr : adj[u]) {
que.emplace_back(u, pr.first);
}
}
while (!que.empty()) {
auto [i, j] = que.front();
que.pop_front();
int di = -1;
for (auto &pr : adj[i])
if (pr.first == j) {
di = pr.second;
break;
}
int od = di ^ 2;
bool revised = false;
vector<int> keep;
for (int p : D[i]) {
bool ok = false;
int bit_i = (p >> di) & 1;
for (int q : D[j]) {
if (((q >> od) & 1) == bit_i) {
ok = true;
break;
}
}
if (ok)
keep.push_back(p);
}
if (keep.size() < D[i].size()) {
D[i].swap(keep);
if (D[i].empty()) {
cout << -1;
return 0;
}
for (auto &pr : adj[i]) {
int k = pr.first;
if (k == j)
continue;
que.emplace_back(k, i);
}
}
}
vector<int> ans(N, -1);
vector<char> seen(N, 0);
vector<char> in_comp(N, 0);
vector<int> comp;
vector<int> local_ans(N, -1);
for (int start = 0; start < N; start++) {
if (ans[start] != -1)
continue;
comp.clear();
deque<int> dq;
dq.push_back(start);
in_comp[start] = 1;
comp.push_back(start);
while (!dq.empty()) {
int u = dq.front();
dq.pop_front();
for (auto &pr : adj[u]) {
int v = pr.first;
if (!in_comp[v]) {
in_comp[v] = 1;
comp.push_back(v);
dq.push_back(v);
}
}
}
for (int u : comp) in_comp[u] = 0;
bool solved = false;
int root = start;
for (int p0 : D[root]) {
for (int u : comp) local_ans[u] = -1;
local_ans[root] = p0;
deque<int> q0;
q0.push_back(root);
bool fail = false;
while (!q0.empty() && !fail) {
int u = q0.front();
q0.pop_front();
for (auto &pr : adj[u]) {
int v = pr.first;
int d = pr.second, od2 = d ^ 2;
int need = (local_ans[u] >> d) & 1;
if (local_ans[v] != -1) {
if (((local_ans[v] >> od2) & 1) != need) {
fail = true;
break;
}
continue;
}
int pick = -1;
for (int qmask : D[v]) {
if (((qmask >> od2) & 1) == need) {
pick = qmask;
break;
}
}
if (pick < 0) {
fail = true;
break;
}
local_ans[v] = pick;
q0.push_back(v);
}
}
if (!fail) {
solved = true;
for (int u : comp) ans[u] = local_ans[u];
break;
}
}
if (!solved) {
cout << -1;
return 0;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << ans[i * m + j] << (j + 1 < m ? ' ' : '\n');
}
}
return 0;
}