欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【搜索】UVa211 —— The Domino Effect

程序员文章站 2022-03-14 19:37:26
...

题目传送门

还是水啊…

预处理出骨牌的编号,然后暴力dfs,完事…

(code by lljd)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN=10;
int lo[MAXN][MAXN],vis[MAXN][MAXN],g[MAXN][MAXN],cnt;
bool tag[30];

void prepare(){
    for(int i=1,j=0,k=0;i<=28;++i,++k){
        if(k>6) ++j,k=j;
        g[j][k]=g[k][j]=i;
    }
    return;
}
bool read(){
    for(int i=0;i<7;++i)
        for(int j=0;j<8;++j)
            if(scanf("%d",&lo[i][j])==EOF) return false;
    return true;
}
void dfs(int cur);
void lay(int x,int y,bool right,int cur){
    int x1=x,y1=y;
    if(right) ++y1;
    else ++x1;
    int a=lo[x][y],b=lo[x1][y1];
    if(g[a][b]&&!tag[g[a][b]]){
        tag[g[a][b]]=true;
        vis[x][y]=vis[x1][y1]=g[a][b];
        dfs(cur+1);
        tag[g[a][b]]=false;
        vis[x][y]=vis[x1][y1]=-1;
    }
    return;
}
void dfs(int cur){
    if(cur==28){
        for(int i=0;i<7;++i){
            for(int j=0;j<8;++j)
                printf("%4d",vis[i][j]);
            printf("\n");
        }
        printf("\n");
        ++cnt;
        return;
    }
    int x=7,y=8;
    for(int i=0;i<7;++i){
        bool flag=true;
        for(int j=0;j<8;++j)
            if(vis[i][j]==-1){
                flag=false;
                x=i,y=j;
                break;
            }
        if(!flag) break;
    }
    if(y+1<8&&vis[x][y+1]==-1) lay(x,y,true,cur);
    if(x+1<7&&vis[x+1][y]==-1) lay(x,y,false,cur);
    return;
}
int solve(){
    cnt=0;
    memset(vis,-1,sizeof(vis));
    memset(tag,0,sizeof(tag));
    dfs(0);
    return cnt;
}
int main(){
    int t=0;
    prepare();
    while(read()){
        if(t) printf("\n\n\n");
        printf("Layout #%d:\n\n",++t);
        for(int i=0;i<7;++i){
            for(int j=0;j<8;++j)
                printf("%4d",lo[i][j]);
            printf("\n");
        }
        printf("\nMaps resulting from layout #%d are:\n\n",t);
        printf("There are %d solution(s) for layout #%d.\n",solve(),t);
    }
}


相关标签: UVa