#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define pii pair<int, int>
#define fr first
#define sc second
#define szof(s) (int)s.size()
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = (int)1e5 + 5;
char C[1025][1025];
char ANS[1025][1025];
int N, M, K;
double BEST;
struct Struct {
int i, j, sz;
Struct () {
i = j = -1;
sz = -1e9;
}
}need;
int get_rand() {
int x = rnd();
if (x < 0) {
x = -x;
}
return x;
}
int toy[4] = {-1, 0, 1, 0};
int tox[4] = {0, 1, 0, -1};
int n, m, k;
char c[1025][1025];
int color[1025][1025];
int sz[(int)1e6 * 2];
int ourColor;
bool in_rectangle(int i, int j) {
return (i >= 1 && i <= n && j >= 1 && j <= m);
}
int kek = 0;
void dfs(int i, int j, int col) {
//cout << "# " << i << " " << j << endl;
kek++;
bool flag = (i == 14 && j == 131);
if (kek >= 25000) {
puts("ok");
cout << i << " " << j << endl;
cout << "kek " << kek << endl;
}
color[i][j] = col;
sz[col]++;
for (int k = 0; k < 4; k++) {
int ii = i + toy[k];
int jj = j + tox[k];
if (!in_rectangle(ii, jj)) {
continue;
}
if (flag) {
cout << "wtf " << ii << " " << jj << endl;
cout << c[ii][jj] << endl;
cout << color[ii][jj] << endl;
while (1) {
int x; cin >> x;
}
}
if (c[ii][jj] == '.' && color[ii][jj] == -1) {
dfs(ii, jj, col);
}
if (flag) {
puts("wtf2");
}
}
}
bool us[1025][1025];
void check_cycle(int y, int x, int py, int px) {
us[y][x] = 1;
for (int k = 0; k < 4; k++) {
int ny = y + toy[k];
int nx = x + tox[k];
if (!in_rectangle(ny, nx)) {
continue;
}
if (c[ny][nx] == '#' || c[ny][nx] == 'X') {
continue;
}
if (ny == py && nx == px) {
continue;
}
if (!us[ny][nx]) {
check_cycle(ny, nx, y, x);
} else {
puts("CYCLE");
exit(0);
}
}
}
bool used[1025][1025]; // 1 our tree
bool check(int y, int x, int py, int px) {
for (int k = 0; k < 4; k++) {
int ny = y + toy[k];
int nx = x + tox[k];
if (!in_rectangle(ny, nx)) {
continue;
}
if (ny == py && nx == px) {
continue;
}
if (c[ny][nx] == '.') {
return false;
}
}
return true;
}
void bfs(int sy, int sx) {
queue <pii> q;
q.push({sy, sx});
c[sy][sx] = '.';
used[sy][sx] = 1;
while (!q.empty()) {
int y = q.front().fr;
int x = q.front().sc;
q.pop();
for (int k = 0; k < 4; k++) {
int ny = y + toy[k];
int nx = x + tox[k];
if (!in_rectangle(ny, nx)) {
continue;
}
if (check(ny, nx, y, x)) {
c[ny][nx] = '.';
used[ny][nx] = 1;
q.push({ny, nx});
}
}
}
}
inline void solve() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (c[i][j] == '.') {
c[i][j] = 'X';
}
}
}
vector <pii> ourPos;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (color[i][j] == ourColor) {
ourPos.push_back({i, j});
}
}
}
int root = get_rand() % szof(ourPos);
int sy = ourPos[root].fr;
int sx = ourPos[root].sc;
bfs(sy, sx);
//puts("answer:");
//for (int i = 1; i <= n; i++) {
//for (int j = 1; j <= m; j++) {
//cout << c[i][j];
//}cout << endl;
//}
check_cycle(ourPos[root].fr, ourPos[root].sc, -1, -1);
}
void init() {
n = N, m = M, k = K;
memset (color, -1, sizeof(color));
memset (sz, 0, sizeof(sz));
memset (us, 0, sizeof(us));
memset (used, 0, sizeof(used));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
c[i][j] = C[i][j];
}
}
}
void SOLVE() {
int id = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (c[i][j] == '.' && color[i][j] == -1) {
cout << "! " << i << " " << j << endl;
dfs(i, j, id);
if (sz[id] > need.sz) {
need.sz = sz[id];
need.i = i;
need.j = j;
ourColor = id;
}
id++;
}
}
}
solve();
int good = 0;
for (int y = 1; y <= n; y++) {
for (int x = 1; x <= m; x++) {
if (c[y][x] == '.') {
int free = 0;
for (int k = 0; k < 4; k++) {
int ny = y + toy[k];
int nx = x + tox[k];
if (!in_rectangle(ny, nx)) {
continue;
}
free += (c[ny][nx] == '.');
}
if (free == 1) {
good++;
}
}
}
}
//cout << "my answer: " << good << endl;
//cout << "k: " << k << endl;
//cout << "score: " << min(10.0, 10.0 * delta) << endl;
double delta = (double)good / (double)k;
double score = min(10.0, 10.0 * delta);
if (score > BEST) {
BEST = score;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
ANS[i][j] = c[i][j];
}
}
}
}
signed main() {
freopen("tin.txt", "r", stdin);
cin >> N >> M >> K;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> C[i][j];
assert(C[i][j] == '.');
}
}
for (int xod = 1; xod <= 1; xod++) {
cout << "xod: " << xod << endl;
init();
SOLVE();
}
puts("_____________________________________________________________________________________________________________");
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cout << ANS[i][j];
}cout << endl;
}
cout << endl << "Best: " << BEST << endl;
}
/*
найти компоненту с большим size'ом
bfs (строить дерево)
*/
