題意:給一副圖,代表多米諾骨牌擺放方式,每兩個連成一塊牌,如0 0 對應1号排 0 1 對應2号排,問圖可以代表幾種擺放方式。
思路:dfs,每個位置的牌不是豎就是橫,枚舉2個方向,最多枚舉28塊,O(2^28),加個剪枝,如果進入枚舉下一行了,目前行還有沒填上的,就直接回溯。
#include<stdio.h>
#include<string.h>
const int d[2][2] = {{1,0},{0,1} };
int cas=0,g[7][8],ans,num[7][7],vis[7][8],res[7][8],v[30];
void init()
{
ans=0;
memset(v,0,sizeof(v));
memset(vis,0,sizeof(vis));
for(int i=0;i<7;i++)
for(int j=0;j<8;j++)
{
if(i==0&&j==0) continue;
scanf("%d",&g[i][j]);
}
}
bool judge(int x){
for(int j=0;j<8;j++)
if(vis[x][j]==0) return true;
return false;
}
void dfs(int x,int y,int nu)
{
if(nu == 28){
ans++;
for(int i=0;i<7;i++)
{
for(int j=0;j<8;j++)
printf("%4d",res[i][j]);
printf("\n");
}
printf("\n");
return;
}
if(x==7) return;
if(y == 8) {
if(judge(x)) return;
dfs(x+1,0,nu);
return;
}
if(vis[x][y]){
dfs(x,y+1,nu);
return;
}
for(int i=0; i<2; i++)
{
if(i==0&&x==6) continue;
if(i==1&&y==7) continue;
int xx=x+d[i][0];
int yy=y+d[i][1];
if(vis[xx][yy]) continue;
if(v[num[g[x][y]][g[xx][yy]]]) continue;
res[x][y] = res[xx][yy]=num[g[x][y]][g[xx][yy]];
vis[x][y]=vis[xx][yy]=v[num[g[x][y]][g[xx][yy]]]=1;
dfs(x,y+1,nu+1);
vis[x][y]=vis[xx][yy]=v[num[g[x][y]][g[xx][yy]]]=0;
}
}
void solve()
{
if(cas) printf("\n\n\n");
printf("Layout #%d:\n\n",++cas);
for(int i=0;i<7;i++)
{
for(int j=0;j<8;j++)
printf("%4d",g[i][j]);
printf("\n");
}
printf("\nMaps resulting from layout #%d are:\n\n", cas);
dfs(0, 0, 0);
printf("There are %d solution(s) for layout #%d.\n", ans, cas);
}
void table()
{
int cnt=1;
for(int i=0;i<=6;i++)
for(int j=i;j<=6;j++){
num[i][j]=num[j][i]=cnt++;
}
}
int main()
{
table();
while(~scanf("%d",&g[0][0]))
{
init();
solve();
}
return 0;
}