【題解】Google Kick Start Round E 2021 – Palindromic Crossword

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int t, n, m;
char g[1005][1005];
vector <int> r[1005], c[1005];

int main() {
    cin >> t;
    for (int Case = 1; Case <= t; Case++){
        cin >> n >> m;
        for (int i = 1; i <= n; i++){
            r[i].clear();
            r[i].push_back(0);
        }
        for (int j = 1; j <= m; j++){
            c[j].clear();
            c[j].push_back(0);
        }
        queue <pair<int, int> > q;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                cin >> g[i][j];
                if (g[i][j] == '#'){
                    r[i].push_back(j);
                    c[j].push_back(i);
                }
                else if (g[i][j] != '.'){
                    q.push({i, j});
                }
            }
        }
        for (int i = 1; i <= n; i++){
            r[i].push_back(m+1);
        }
        for (int j = 1; j <= m; j++){
            c[j].push_back(n+1);
        }
        int cnt = 0;
        while (!q.empty()){
            int x = q.front().first, y = q.front().second;
            q.pop();
            int tmp = lower_bound(r[x].begin(), r[x].end(), y)-r[x].begin();
            int tar = r[x][tmp]+r[x][tmp-1]-y;
            if (g[x][tar] == '.'){
                cnt++;
                g[x][tar] = g[x][y];
                q.push({x, tar});
            }
            tmp = lower_bound(c[y].begin(), c[y].end(), x)-c[y].begin();
            tar = c[y][tmp]+c[y][tmp-1]-x;
            if (g[tar][y] == '.'){
                cnt++;
                g[tar][y] = g[x][y];
                q.push({tar, y});
            }
        }
        cout << "Case #" << Case << ": " << cnt << "\n";
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                cout << g[i][j];
            }
            cout << "\n";
        }
    }
}