KNIGHTS (CSP TST)

#define taskname "KNIGHTS"
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int maxMN = 400;
const int maxV = maxMN * maxMN;
char a[maxMN][maxMN];
int m, n, nvertices;
int dx[8]{1, -1, 1, -1, 2, -2, 2, -2};
int dy[8]{2, 2, -2, -2, 1, 1, -1, -1};
vector<int> adj[maxV];
vector<int> z;
int match[maxV], avail[maxV];
bool found;

inline bool Valid(int i, int j)
{
    return i >= 0 && i < m && j >= 0 && j < n && a[i][j] == '.';
}

inline bool IsBlack(int i, int j)
{
    return a[i][j] == '.' && bool((i + j) & 1);
}

inline bool IsWhite(int i, int j)
{
    return a[i][j] == '.' && !bool((i + j) & 1);
}

inline int Encode(int i, int j)
{
    return i * n + j;
}

void Enter()
{
    cin >> m >> n;
    nvertices = m * n;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            cin >> a[i][j];
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (IsWhite(i, j))
            {
                int x = Encode(i, j);
                z.push_back(x);
                for (int d = 0; d < 8; ++d)
                    if (Valid(i + dx[d], j + dy[d]))
                        adj[x].push_back(Encode(i + dx[d], j + dy[d]));
            }
    fill_n(match, nvertices, -1);
}

void DFS(int x)
{
    for (int y: adj[x])
        if (avail[y])
        {
            avail[y] = false;
            if (match[y] == -1) found = true;
            else DFS(match[y]);
            if (found)
            {
                match[y] = x;
                return;
            }
        }
}

void Solve()
{
    unsigned OldSize;
    do
    {
        fill_n(avail, nvertices, true);
        OldSize = z.size();
        for (int i = z.size() - 1; i >= 0; --i)
        {
            found = false;
            DFS(z[i]);
            if (found)
            {
                z[i] = z.back(); z.pop_back();
            }
        }
    }
    while (OldSize != z.size());
}


bool SelX[maxV], SelY[maxV];
void GetRes()
{
    fill_n(avail, nvertices, true);
    for (int x: z) DFS(x);
    fill_n(SelY, nvertices, false);
    int y;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (IsBlack(i, j) && !avail[y = Encode(i, j)])
                SelY[y] = true;
    fill_n(SelX, nvertices, false);
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (IsBlack(i, j) && match[y = Encode(i, j)] != -1)
                if (!SelY[y]) SelX[match[y]] = true;
    int res = 0;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (a[i][j] == '.')
            {
                a[i][j] = 'K'; ++ res;
            }
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
        {
            int k = Encode(i, j);
            if (SelX[k] || SelY[k])
            {
                a[i][j] = '.'; --res;
            }
        }
    cout << res << '\n';
    for (int i = 0; i < m; ++i, cout << '\n')
        for (int j = 0; j < n; ++j) cout << a[i][j];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
    Enter();
    Solve();
    GetRes();
}