紫书搜索习题7-3 UVA

题目链接:

题意:

给一副图，代表多米诺骨牌摆放方式，每两个连成一块牌，如0 0 对应1号排 0 1 对应2号排，问图可以代表几种摆放方式。

题解:

dfs，每个位置的牌不是竖就是横，枚举2个方向，最多枚举28块,O(2^28),加个剪枝，如果进入枚举下一行了，当前行还有没填上的，就直接回溯。

代码:

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 #define MS(a) memset(a,0,sizeof(a))
  5 #define MP make_pair
  6 #define PB push_back
  7 const int INF = 0x3f3f3f3f;
  8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  9 inline ll read(){
 10     ll x=0,f=1;char ch=getchar();
 11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 13     return x*f;
 14 }
 15 //////////////////////////////////////////////////////////////////////////
 16 const int maxn = 1e5+10;
 17 
 18 int num[8][9],g[8][9];
 19 int res[10][10],vis[10][10],v[30];
 20 int dir[2][2] = {{1,0},{0,1}};
 21 int ans;
 22 
 23 void table(){
 24     int cnt = 1;
 25     for(int i=0; i<7; i++)
 26         for(int j=i; j<7; j++)
 27             num[i][j] = num[j][i] = cnt++;
 28 }
 29 
 30 bool ok(int x){
 31     for(int i=0; i<8; i++)
 32         if(vis[x][i] == 0) return false;
 33     return true;
 34 }
 35 
 36 void dfs(int x,int y,int nu){
 37     if(nu == 28){
 38         ans++;
 39         for(int i=0; i<7; i++){
 40             for(int j=0; j<8; j++)
 41                 printf("%4d",res[i][j]);
 42             puts("");
 43         }
 44         puts("");
 45         return ;
 46     }
 47 
 48     if(x==7) return ;
 49     if(y==8){
 50         if(!ok(x)) return ;  // 这一行没有都被覆盖，这种解不行，回溯
 51         dfs(x+1,0,nu);
 52         return ;
 53     }
 54 
 55     if(vis[x][y]){
 56         dfs(x,y+1,nu);
 57         return ;
 58     }
 59 
 60     for(int i=0; i<2; i++){
 61         if(i==0 && x==6) continue;
 62         if(i==1 && y==7) continue;
 63         int tx=x+dir[i][0], ty=y+dir[i][1];
 64         int k = num[g[x][y]][g[tx][ty]];
 65         if(vis[tx][ty]) continue;
 66         if(v[k]) continue;
 67         res[x][y] = res[tx][ty] = k;
 68         vis[x][y] = vis[tx][ty] = v[k] = 1;
 69         dfs(x,y+1,nu+1);
 70         vis[x][y] = vis[tx][ty] = v[k] = 0;
 71     }
 72 }
 73 
 74 int main(){
 75     table();
 76     int cas=0;
 77     while(~scanf("%d",&g[0][0])){
 78         MS(vis); MS(v); ans=0;
 79         if(cas) printf("


");
 80         for(int i=0; i<7; i++)
 81             for(int j=0; j<8; j++){
 82                 if(i==0 && j==0) continue;
 83                 scanf("%d",&g[i][j]);
 84             }
 85 
 86         printf("Layout #%d:

",++cas);
 87         for(int i=0; i<7; i++){
 88             for(int j=0; j<8; j++)
 89                 printf("%4d",g[i][j]);
 90             puts("");
 91         }
 92         puts("");
 93 
 94         printf("Maps resulting from layout #%d are:

",cas);
 95         dfs(0,0,0);
 96         printf("There are %d solution(s) for layout #%d.
",ans,cas);
 97     }
 98 
 99     return 0;
100 }

紫书搜索 习题7-3 UVA

题目链接:

题意:

题解:

代码:

紫书搜索习题7-3 UVA