[ABC326D] ABC Puzzle 题解

题意：

给定整数 \(N\)，字符串 \(R,C\)，构造满足以下条件的 \(N\times N\) 矩阵：

1.每一行和每一列中 \(A,B,C\) 各有且仅有一个。

2.第 \(i\) 行的第一个字母等于字符串 \(R\) 的第 \(i\) 个字符。

3.第 \(i\) 列的第一个字母等于字符串 \(C\) 的第 \(i\) 个字符。

看数据范围考虑应该是搜索，首先先构造一个满足条件 1 的矩阵，然后再检查是否满足条件 2，3 即可。使用 \(dfs(line,num)\) 表示填到了第 \(line\) 行，第 \(num\) 个字符，逐行填入，每次填的时候判断一次是否满足条件 1，最后判断是否满足条件 2，3 即可。

上代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, flag;
string s1, s2;
char c[10][10];
void print()
{
    cout << "Yes" << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << c[i][j];
        cout << endl;
    }
    return;
}
bool judge(int x, int y, char z) {//判断第x行第y列能否填入字母z
    for (int i = 1; i < x; i++)
        if (c[i][y] == z) return false;
    if (c[x][y] != '.') return false;
    return true;
}
bool judge2() {
    char t;
    for (int i = 1; i <= n; i++) {//第i行第一个字母
        for (int j = 1; j <= n; j++)
            if (c[i][j] != '.') {
                t = c[i][j];
                break;
            }
        if (t != s1[i - 1]) return false;
    }
    for (int i = 1; i <= n; i++) {//第i列第一个字母
        for (int j = 1; j <= n; j++)
            if (c[j][i] != '.') {
                t = c[j][i];
                break;
            }
        if (t != s2[i - 1]) return false;
    }
    return true;
}
void dfs(int line, int num)//当前正在填入第line行，第num个字母
{
    if (flag) return;
    if (line == n + 1) {
        if (judge2()) {
            print();
            flag = 1;
        }
        return;
    }
    char now = 'A' + num - 1;
    for (int i = 1; i <= n; i++) {
        if (judge(line, i, now)) {
            c[line][i] = now;
            dfs(num == 3 ? line + 1 : line, num == 3 ? 1 : num + 1);
            c[line][i] = '.';
        }
    }
}
int main()
{
    cin >> n >> s1 >> s2;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            c[i][j] = '.';
    dfs(1, 1);
    if (!flag) cout << "No" << endl;
    return 0;
}