Palindromic Crossword

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

#define all(x) (x).begin(),(x).end()
#define pb push_back
#define pf push_front
#define sz(x) (int)(x).size()
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define fi first
#define se second
#define setbits(x) __builtin_popcount(x)
#define zerobits(x) __builtin_ctz(x)
#define setbitsll(x) __builtin_popcountll(x)
#define zerobitsll(x) __builtin_ctzll(x)
#define ps(x,y) fixed<<setprecision(y)<<x

typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
typedef map<int,int> mii;

const int MOD = 1e9+7;
const ld PI = acos((ld)-1);
const int maxN = 1005;

string grid[maxN],res[maxN];
int row1[maxN][maxN],col1[maxN][maxN],row2[maxN][maxN],col2[maxN][maxN],n,m;
bool visited[maxN][maxN];

void dfs(int r,int c,char ch) {
    if (r < 0 || c < 0 || r >= n || c >= m) return;
    res[r][c] = ch;
    visited[r][c] = true;
    int u = col1[r][c]+1;
    int d = col2[r][c]-1;
    int mirrorVertial = d-r+u;
    if (mirrorVertial >= 0 && mirrorVertial < n && !visited[mirrorVertial][c] && grid[mirrorVertial][c] != '#') {
        dfs(mirrorVertial,c,ch);
    }
    int left = row1[r][c]+1;
    int right = row2[r][c]-1;
    int mirrorHorizontal = right-c+left;
    if (mirrorHorizontal >= 0 && mirrorHorizontal < m && !visited[r][mirrorHorizontal] && grid[r][mirrorHorizontal] != '#') {
        dfs(r,mirrorHorizontal,ch);
    }

}

void solve () {
    cin >> n >> m;
    for (int i = 0;i < n;++i) {
        cin >> grid[i];
    }
    for (int i = 0;i < n;++i) {
        for (int j = 0;j < m;++j) {
            res[i][j] = grid[i][j];
            visited[i][j] = false;
            row1[i][j] = col1[i][j] = -1;
            row2[i][j] = m;
            col2[i][j] = n;
        }
    }
    for (int i = 0;i < n;++i) {
        for (int j = 0;j < m;++j) {
            if (grid[i][j] == '#') {
                row1[i][j] = j;
            } else {
                if (j) {
                    row1[i][j] = row1[i][j-1];
                }
            }
        }
        for (int j = m-1;j >= 0;--j) {
            if (grid[i][j] == '#') {
                row2[i][j] = j;
            } else {
                if (j < m-1) {
                    row2[i][j] = row2[i][j+1];
                }
            }
        }
    }
    for (int j = 0;j < m;++j) {
        for (int i = 0;i < n;++i) {
            if (grid[i][j] == '#') {
                col1[i][j] = i;
            } else {
                if (i) {
                    col1[i][j] = col1[i-1][j];
                }
            }
        }
        for (int i = n-1;i >= 0;--i) {
            if (grid[i][j] == '#') {
                col2[i][j] = i;
            } else {
                if (i < n-1) {
                    col2[i][j] = col2[i+1][j];
                }
            }
        }

    }
    for (int i = 0;i < n;++i) {
        for (int j = 0;j < m;++j) {
            if (grid[i][j] != '.' && grid[i][j] != '#' && !visited[i][j]) {
                dfs(i,j,grid[i][j]);
            }
        }
    }
    int cnt = 0;
    for (int i = 0;i < n;++i) {
        for (int j = 0;j < m;++j) {
            if (grid[i][j] == '.' && res[i][j] != '.') ++cnt;
        }
    }
    cout << cnt << '\n';
    for (int i = 0;i < n;++i) {
        for (int j = 0;j < m;++j) {
            cout << res[i][j];
        }
        cout << '\n';
    }
}

int main () {

#ifndef ONLINE_JUDGE
 freopen("input1.txt","r",stdin);
 freopen("output1.txt","w",stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    for (int tc = 1;tc <= t;++tc) {
        cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}