#include <algorithm>
#include <array>
#include <atomic>
#include <fstream>
#include <iostream>
#include <climits>
#include <cmath>
#include <iomanip>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <thread>
#include <vector>
using namespace std;
constexpr int N = 100;
constexpr int C = 26;
vector<vector<int>> T(C);
vector<vector<int>> D(C);
int loss = 0;
vector<string> L(N);
vector<pair<int, int>> pos(C);
void setPos(int i, int r, int c) {
L[pos[i].first][pos[i].second] = '.';
pos[i] = {r, c};
L[pos[i].first][pos[i].second] = 'A' + i;
}
constexpr int TC = 4;
vector<vector<int>> dt[TC];
constexpr int FAR = INT_MAX / 4;
void bfs(int i, vector<vector<int>>& d) {
d.resize(N);
for(int i = 0; i < N; ++i) {
d[i].resize(N);
fill(d[i].begin(), d[i].end(), FAR);
}
queue<pair<int, int>> Q;
d[pos[i].first][pos[i].second] = 0;
Q.push(pos[i]);
while(!Q.empty()) {
auto [r, c] = Q.front();
Q.pop();
for(auto [dr, dc] : array<pair<int, int>, 4>{{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}}) {
int r2 = r + dr;
int c2 = c + dc;
if(L[r2][c2] != '#' && d[r2][c2] == FAR) {
d[r2][c2] = d[r][c] + 1;
Q.push({r2, c2});
}
}
}
for(int j = 0; j < C; ++j) {
auto [r, c] = pos[j];
if(d[r][c] < 0) {
throw 5;
}
D[i][j] = d[r][c];
}
}
void update() {
vector<thread> threads;
atomic<int> nextIdx = 0;
for(int ti = 0; ti < TC; ++ti) {
threads.emplace_back([ti, &nextIdx]() {
while(true) {
int i = nextIdx.fetch_add(1);
if(i >= C) {
break;
}
bfs(i, dt[ti]);
}
});
}
for(thread& t : threads) {
t.join();
}
loss = 0;
for(int i = 0; i < C; ++i) {
for(int j = 0; j < C; ++j) {
if(D[i][j] >= FAR) {
loss = FAR;
return;
}
loss += abs(D[i][j] - T[i][j]);
// if(D[i][j] != T[i][j]) {
// ++loss;
// }
}
}
}
int main() {
cin.sync_with_stdio(false);
cin.tie(nullptr);
mt19937 rng(1234321);
ifstream fp("laby.txt");
for(int i = 0; i < C; ++i) {
T[i].resize(C);
D[i].resize(C);
for(int j = 0; j < C; ++j) {
fp >> T[i][j];
}
}
if(!fp.good()) throw 5;
for(int i = 0; i < N; ++i) {
cin >> L[i];
if(L[i].size() != N) {
throw 5;
}
}
for(int i = 0; i < C; ++i) {
bool found = false;
for(int r = 0; r < N; ++r) {
for(int c = 0; c < N; ++c) {
if((r == 0 || c == 0 || r == N - 1 || c == N - 1) && L[r][c] != '#') {
throw 5;
}
if(L[r][c] == ('A' + i)) {
if(found) {
throw 5;
}
found = true;
pos[i] = {r, c};
}
}
}
if(!found) {
throw 5;
}
}
{
update();
int asd = 0;
int bsd = 0;
for(int i = 0; i < C; ++i) {
for(int j = 0; j < C; ++j) {
if(T[i][j] == D[i][j]) {
++asd;
}
++bsd;
}
}
cerr << -1 << " " << loss << " " << 100.0 * (double)asd / (double)bsd << "\n";
}
for(int iter = 0; ; ++iter) {
int best = INT_MAX;
vector<tuple<bool, int, int, int>> bestMoves;
for(int i = 0; i < C; ++i) {
auto [r, c] = pos[i];
for(int dr = -3; dr <= 3; ++dr) {
for(int dc = -3; dc <= 3; ++dc) {
int r2 = r + dr;
int c2 = c + dc;
if(r2 >= 1 && c2 >= 1 && r2 < N - 1 && c2 < N - 1 && (L[r2][c2] == '.' || L[r2][c2] == '#')) {
char old = L[r2][c2];
setPos(i, r2, c2);
update();
if(loss < best) {
best = loss;
bestMoves.clear();
}
if(loss == best) {
bestMoves.push_back({true, i, r2, c2});
}
setPos(i, r, c);
L[r2][c2] = old;
}
}
}
{
int r2 = uniform_int_distribution<int>(1, N - 2)(rng);
int c2 = uniform_int_distribution<int>(1, N - 2)(rng);
if(L[r2][c2] == '.' || L[r2][c2] == '#') {
char old = L[r2][c2];
setPos(i, r2, c2);
update();
if(loss < best) {
best = loss;
bestMoves.clear();
}
if(loss == best) {
bestMoves.push_back({true, i, r2, c2});
}
setPos(i, r, c);
L[r2][c2] = old;
}
}
}
for(int asd = 0; asd < 100; ++asd) {
int r = uniform_int_distribution<int>(1, N - 2)(rng);
int c = uniform_int_distribution<int>(1, N - 2)(rng);
if(L[r][c] == '#') {
L[r][c] = '.';
update();
if(loss < best) {
best = loss;
bestMoves.clear();
}
if(loss == best) {
bestMoves.push_back({false, '.', r, c});
}
L[r][c] = '#';
}
if(L[r][c] == '.') {
L[r][c] = '#';
update();
if(loss < best) {
best = loss;
bestMoves.clear();
}
if(loss == best) {
bestMoves.push_back({false, '#', r, c});
}
L[r][c] = '.';
}
}
if(bestMoves.empty()) {
throw 5;
}
auto [t, i, r2, c2] = bestMoves[uniform_int_distribution<int>(0, (int)bestMoves.size() - 1)(rng)];
if(t) {
setPos(i, r2, c2);
} else {
L[r2][c2] = (char)i;
}
update();
if(loss != best) {
throw 5;
}
int asd = 0;
int bsd = 0;
for(int i = 0; i < C; ++i) {
for(int j = 0; j < C; ++j) {
if(T[i][j] == D[i][j]) {
++asd;
}
++bsd;
}
}
cerr << iter << " " << best << " " << 100.0 * (double)asd / (double)bsd << "\n";
if(iter % 20 == 0) {
cerr << "SAVE\n";
ofstream fp("labyrintti2.out");
for(int i = 0; i < N; ++i) {
fp << L[i] << "\n";
}
fp.close();
}
}
return 0;
}
