Knit the Grid

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

struct TwoSAT {
    int n;
    vector<vector<int>> g, rg;

    TwoSAT(int n = 0) : n(n), g(2 * n), rg(2 * n) {}

    int id(int v, int val) const { return 2 * v + val; }

    void imply(int a, int b) {
        g[a].push_back(b);
        rg[b].push_back(a);
    }

    void add_or(int x, int xv, int y, int yv) {
        imply(id(x, xv ^ 1), id(y, yv));
        imply(id(y, yv ^ 1), id(x, xv));
    }

    void add_unit(int x, int xv) {
        imply(id(x, xv ^ 1), id(x, xv));
    }

    void add_equal_expr(int x, int xc, int y, int yc) {
        // (value[x] ^ xc) == (value[y] ^ yc)
        add_or(x, xc, y, yc ^ 1);
        add_or(y, yc, x, xc ^ 1);
    }

    bool solve(vector<int>& ans) {
        int m = 2 * n;
        vector<int> order, comp(m, -1), vis(m, 0);
        order.reserve(m);

        for (int s = 0; s < m; s++) if (!vis[s]) {
            vector<pair<int, int>> st = {{s, 0}};
            vis[s] = 1;
            while (!st.empty()) {
                int v = st.back().first;
                int &it = st.back().second;
                if (it < (int)g[v].size()) {
                    int to = g[v][it++];
                    if (!vis[to]) {
                        vis[to] = 1;
                        st.push_back({to, 0});
                    }
                } else {
                    order.push_back(v);
                    st.pop_back();
                }
            }
        }

        int cc = 0;
        for (int z = m - 1; z >= 0; z--) {
            int s = order[z];
            if (comp[s] != -1) continue;
            vector<int> st = {s};
            comp[s] = cc;
            while (!st.empty()) {
                int v = st.back();
                st.pop_back();
                for (int to : rg[v]) if (comp[to] == -1) {
                    comp[to] = cc;
                    st.push_back(to);
                }
            }
            cc++;
        }

        ans.assign(n, 0);
        for (int i = 0; i < n; i++) {
            if (comp[2 * i] == comp[2 * i + 1]) return false;
            ans[i] = comp[2 * i] < comp[2 * i + 1];
        }
        return true;
    }
};

int main() {
    setIO();

    int T;
    cin >> T;
    while (T--) {
        int r, c;
        cin >> r >> c;

        vector<string> a(r);
        for (string &s : a) cin >> s;

        int diagCnt = r + c + 1;
        int offQ = diagCnt;
        int vars = 2 * diagCnt;

        vector<vector<int>> pc(r + 1, vector<int>(c + 1, 0));
        vector<vector<int>> qc(r + 1, vector<int>(c + 1, 0));

        for (int s = 0; s <= r + c; s++) {
            vector<pair<int, int>> pts;
            for (int i = max(0, s - c); i <= min(r, s); i++) {
                pts.push_back({i, s - i});
            }
            for (int t = 0; t + 1 < (int)pts.size(); t++) {
                auto [i, j] = pts[t];
                auto [ni, nj] = pts[t + 1];
                pc[ni][nj] = pc[i][j] ^ (a[i][j - 1] == 'B');
            }
        }

        for (int d = -r; d <= c; d++) {
            vector<pair<int, int>> pts;
            for (int i = max(0, -d); i <= min(r, c - d); i++) {
                pts.push_back({i, i + d});
            }
            for (int t = 0; t + 1 < (int)pts.size(); t++) {
                auto [i, j] = pts[t];
                auto [ni, nj] = pts[t + 1];
                qc[ni][nj] = qc[i][j] ^ (a[i][j] == 'B');
            }
        }

        TwoSAT sat(vars);

        auto exprP = [&](int i, int j) -> pair<int, int> {
            return {i + j, pc[i][j]};
        };
        auto exprQ = [&](int i, int j) -> pair<int, int> {
            return {offQ + (j - i + r), qc[i][j]};
        };
        auto cell = [&](int i, int j) -> int {
            if (i < 0 || i >= r || j < 0 || j >= c) return -1;
            return i * c + j;
        };

        vector<int> firstVar(r * c, -1), firstConst(r * c, 0);

        auto add_boundary_expr = [&](pair<int, int> e, int u, int v) {
            if (u == -1 && v == -1) {
                sat.add_unit(e.first, e.second);
            } else if ((u == -1) != (v == -1)) {
                int id = (u == -1 ? v : u);
                if (firstVar[id] == -1) {
                    firstVar[id] = e.first;
                    firstConst[id] = e.second;
                } else {
                    sat.add_equal_expr(firstVar[id], firstConst[id], e.first, e.second);
                }
            }
        };

        for (int i = 0; i <= r; i++) {
            for (int j = 0; j <= c; j++) {
                add_boundary_expr(exprP(i, j), cell(i - 1, j - 1), cell(i, j));
                add_boundary_expr(exprQ(i, j), cell(i - 1, j), cell(i, j - 1));
            }
        }

        for (int i = 1; i < r; i++) {
            for (int j = 1; j < c; j++) {
                auto [pv, pcst] = exprP(i, j);
                auto [qv, qcst] = exprQ(i, j);
                sat.add_or(pv, pcst ^ 1, qv, qcst ^ 1);
            }
        }

        vector<int> val;
        if (!sat.solve(val)) {
            cout << "NO\n";
            continue;
        }

        auto P = [&](int i, int j) {
            auto [v, cs] = exprP(i, j);
            return val[v] ^ cs;
        };
        auto Q = [&](int i, int j) {
            auto [v, cs] = exprQ(i, j);
            return val[v] ^ cs;
        };

        vector<string> x(r, string(c, '0'));
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                int bit;
                if (i == 0 || j == 0) bit = P(i, j);
                else bit = (x[i - 1][j - 1] - '0') ^ P(i, j);
                x[i][j] = char('0' + bit);
            }
        }

        auto get = [&](int i, int j) {
            if (i < 0 || i >= r || j < 0 || j >= c) return 0;
            return x[i][j] - '0';
        };

        bool ok = true;
        for (int i = 0; i <= r && ok; i++) {
            for (int j = 0; j <= c; j++) {
                if ((get(i - 1, j - 1) ^ get(i, j)) != P(i, j)) ok = false;
                if ((get(i - 1, j) ^ get(i, j - 1)) != Q(i, j)) ok = false;
            }
        }

        if (!ok) {
            cout << "NO\n";
            continue;
        }

        cout << "YES\n";
        for (int i = 0; i <= r; i++) {
            string s;
            s.reserve(c);
            for (int j = 0; j < c; j++) {
                s.push_back(char('0' + (get(i - 1, j) ^ get(i, j))));
            }
            cout << s << '\n';
        }
        for (int i = 0; i < r; i++) {
            string s;
            s.reserve(c + 1);
            for (int j = 0; j <= c; j++) {
                s.push_back(char('0' + (get(i, j - 1) ^ get(i, j))));
            }
            cout << s << '\n';
        }
    }
}