# 【題解】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";
}
}
}

```