【搜索】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);
}
}
上一篇: 2020.7.15集训
下一篇: 算法竞赛入门经典 习题2-6 排列