Đáp án:#include <iostream>
#include <vector>
#include <string>

using namespace std;

// Mảng hướng để kiểm tra 4 ô kề cạnh (Trái, Phải, Trên, Dưới)
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

void solve(int test_num) {
    int n;
    cin >> n;
    vector<string> grid(n);
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }

    // Duyệt qua từng ô theo thứ tự hàng và cột
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < n; ++c) {
            // Nếu ô là ô trống, tìm chữ cái hợp lệ nhỏ nhất
            if (grid[r][c] == '.') {
                for (char ch = 'A'; ch <= 'Z'; ++ch) {
                    bool ok = true;
                    // Kiểm tra 4 ô xung quanh xem có bị trùng chữ cái không
                    for (int k = 0; k < 4; ++k) {
                        int nr = r + dx[k];
                        int nc = c + dy[k];
                        if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                            if (grid[nr][nc] == ch) {
                                ok = false;
                                break;
                            }
                        }
                    }
                    // Nếu hợp lệ thì gán ký tự ch và dừng tìm kiếm
                    if (ok) {
                        grid[r][c] = ch;
                        break;
                    }
                }
            }
        }
    }

    // In kết quả cho test
    cout << "Case " << test_num << ":\n";
    for (int i = 0; i < n; ++i) {
        cout << grid[i] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    if (cin >> t) {
        for (int i = 1; i <= t; ++i) {
            solve(i);
        }
    }
    return 0;
}

Giải thích các bước giải:

Vì đề yêu cầu kết quả có thứ tự từ điển nhỏ nhất, ta có thể duyệt lần lượt từng ô $(i, j)$ từ trên xuống dưới, từ trái sang phải:

1. Nếu ô $(i, j)$ đã được điền sẵn chữ cái, ta giữ nguyên.

2. Nếu ô $(i, j)$ là ô trống ('.'), ta thử chọn ký tự nhỏ nhất có thể bắt đầu từ 'A', 'B', 'C',...

3. Ký tự hợp lệ chọn cho ô $(i, j)$ là ký tự khác với ký tự ở các ô chung cạnh đã có giá trị (ô bên trên $(i-1, j)$, ô bên dưới $(i+1, j)$, ô bên trái $(i, j-1)$, ô bên phải $(i, j+1)$).

4. Do quy luật thứ tự từ điển, việc chọn ký tự hợp lệ nhỏ nhất cho từng ô theo thứ tự đọc (từ trên xuống, trái sang phải) luôn cho ra kết quả tối ưu toàn cục.