Google Kick Start 2021 Round E - C(Parlindromic Crossword)

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

int main() {
	int T;
	scanf("%d", &T);
	
	for(int tc = 1; tc <= T; tc++) {
		int N, M;
		scanf("%d %d", &N, &M);
		
		char temp;
		scanf("%c", &temp);
		vector<vector<int>> grid(N);
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				scanf("%c", &temp);
				int a = (int)temp;
				if(a == 46) {
					grid[i].push_back(0);
				}
				else if(a == 35) {
					grid[i].push_back(-1);
				}
				else
					grid[i].push_back(a-64);
			}
			scanf("%c", &temp);
		}
		vector<vector<pair<int,int>>> row(N);
		vector<vector<pair<int,int>>> col(M);
		vector<vector<int>> row_num(N);
		vector<vector<int>> col_num(M);
		for(int i = 0; i < N; i++) {
			bool state = false;
			int count = 0;
			for(int j = 0; j < M; j++) {
				row_num[i].push_back(-1);
				if(!state) {
					if(grid[i][j] >= 0) {
						row[i].push_back(make_pair(j,j));
						row_num[i][j] = count;
						state = true;
					}
				}
				else {
					if(grid[i][j] >= 0) {
						row[i][count].second++;
						row_num[i][j] = count;
					}
					else{
						count++;
						state = false;
					}
				}
			}
		}
		for(int i = 0; i < M; i++) {
			bool state = false;
			int count = 0;
			for(int j = 0; j < N; j++) {
				col_num[i].push_back(-1);
				if(!state) {
					if(grid[j][i] >= 0) {
						col[i].push_back(make_pair(j,j));
						col_num[i][j] = count;
						state = true;
					}
				}
				else {
					if(grid[j][i] >= 0) {
						col[i][count].second++;
						col_num[i][j] = count;
					}
					else{
						count++;
						state = false;
					}
				}
			}
		}
        
		vector<vector<int>> new_grid(N);
		vector<vector<bool>> check(N);
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				new_grid[i].push_back(grid[i][j]);
				check[i].push_back(false);
			}
		}
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(check[i][j]) continue;
				if(new_grid[i][j] <= 0) continue;
				check[i][j] = true;
				int a = new_grid[i][j];
				pair<int, int> cur = make_pair(i, row[i][row_num[i][j]].first + row[i][row_num[i][j]].second - j);
				int state = 0;
				while(!check[cur.first][cur.second]) {
					new_grid[cur.first][cur.second] = a;
					check[cur.first][cur.second] = true;
					if(state == 0) {
						cur = make_pair(col[cur.second][col_num[cur.second][cur.first]].first + col[cur.second][col_num[cur.second][cur.first]].second - cur.first, cur.second);					
						state = 1;
					}
					else {
						cur = make_pair(cur.first, row[cur.first][row_num[cur.first][cur.second]].first + row[cur.first][row_num[cur.first][cur.second]].second - cur.second);
						state = 0;
					}
				}
				
				cur = make_pair(col[j][col_num[j][i]].first + col[j][col_num[j][i]].second - i, j);
				state = 1;
				while(!check[cur.first][cur.second]) {
					new_grid[cur.first][cur.second] = a;
					check[cur.first][cur.second] = true;
					if(state == 0) {
						cur = make_pair(col[cur.second][col_num[cur.second][cur.first]].first + col[cur.second][col_num[cur.second][cur.first]].second - cur.first, cur.second);
						state = 1;
					}
					else {
						cur = make_pair(cur.first, row[cur.first][row_num[cur.first][cur.second]].first + row[cur.first][row_num[cur.first][cur.second]].second - cur.second);
						state = 0;
					}
				}
			}
		}
		int count = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++)
				if(grid[i][j] == 0 && new_grid[i][j] > 0) count++;
		}
		printf("Case #%d: %d\n", tc, count);
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(new_grid[i][j] == -1) printf("#");
				else if(new_grid[i][j] == 0) printf(".");
				else printf("%c", (char)(new_grid[i][j]+64));
			}
			printf("\n");
		}
	}
}