[ABC326D]搜索+剪枝

moonky128 · 2023-10-30 15:12:56 · 题解

爆搜剪枝，碰到不合法的状态直接剪掉就行了。

考虑 n=5 时每行的合法状态数，一行中只包含三种字母各一个，且第一个字母的顺序确定，则有两种合法状态数的计算方法：

下文称第 i 个字母的位置为 pl_i。

• 按第一个字母的位置分讨（显然有 pl_1\in[1,3]）：

  • 于是每行的合法状态数为 4\times3+3\times2+2\times1=20。

• 先计算三个字母的排列方案（5\times4\times3），因为每行第一个字母确定，所以要把第一个字母不合法的状态去掉，即 \frac{5\times4\times3}3=20。

一共 5 行，所以保证每行状态合法的情况下总状态数为 20^5=3.2\times 10^6，\text{4s} 完全够跑了。

#include<bits/stdc++.h>
#define N 15
using namespace std;
int n,ro[N][4],col[N][4];
char r[N],c[N],ans[N][N];
void dfs(int,int,int);
signed main(){
    scanf("%d%s%s",&n,r+1,c+1);
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) ans[i][j]='.';
    dfs(1,1,0);
    printf("No");
    return 0;
}
void dfs(int x,int y,int ly){
    if(x>n){
        printf("Yes\n");
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j)
                putchar(ans[i][j]);
            putchar('\n');
        }
        exit(0);
    }
    if(ly>n+y-4) return ;
    if(y>3) dfs(x+1,1,0);
    for(int i=ly+1;i<=n;++i){
        if(y==1){
            if(!col[i][c[i]-'A']){
                if(r[x]!=c[i]) continue;
                else
                    ans[x][i]=r[x],col[i][c[i]-'A']=x,ro[x][r[x]-'A']=i,dfs(x,y+1,i),
                    ans[x][i]='.',col[i][c[i]-'A']=0,ro[x][r[x]-'A']=0;
            }
            else if(col[i][r[x]-'A']) continue;
            else
                ans[x][i]=r[x],col[i][r[x]-'A']=x,ro[x][r[x]-'A']=i,dfs(x,y+1,i),
                ans[x][i]='.',col[i][r[x]-'A']=0,ro[x][r[x]-'A']=0;
            continue;
        }
        for(int j=0;j<3;++j){
            if(ro[x][j]||col[i][j]||(!col[i][c[i]-'A']&&c[i]-'A'!=j)) continue;
            ans[x][i]='A'+j,col[i][j]=x,ro[x][j]=i,dfs(x,y+1,i),
            ans[x][i]='.',col[i][j]=0,ro[x][j]=0;
        }
        dfs(x,y,i);
    }
}