UVA 211 The Domino Effect 多米诺效应 （回溯）

骨牌无非两种放法，横着或竖着放，每次检查最r，c最小的没访问过的点即可。如果不能放就回溯。

最外面加一层认为已经访问过的位置，方便判断。

#include<bits/stdc++.h>

const int MAXD = 56;
const int MAXB = 29;
const int MAXP = 7;

bool used[MAXB];// used Bone
int pip[MAXP][MAXP];// pip 2 Bone

int tab[7][8];
int ans[8][9];

int cnt;
void dfs(int r,int c)
{
    while(ans[r][c]) {
        if(c == 8) { r++; c = -1; }
        c++;
    }
    if(r == 7) {
        for(int i = 0; i < 7; i++){
        for(int j = 0; j < 8; j++){
            printf("%4d",ans[i][j]);
        }
        putchar('
');
    }
    putchar('
');
        cnt++;
        return ;
    }

    int &p0 = tab[r][c];
    if(!ans[r][c+1]){ // 横着放
        int &p1 = tab[r][c+1];
        int &bone = pip[p0][p1];
        if(!used[bone]){
            used[bone] = 1;
            ans[r][c+1] = ans[r][c] = bone;
            dfs(r,c+1);
            ans[r][c+1] = ans[r][c] = 0;
            used[bone] = 0;
        }
    }

    if(!ans[r+1][c]) { //竖着放
         int &p2 = tab[r+1][c];
         int &bone = pip[p0][p2];
         if(!used[bone]){
            used[bone] = 1;
            ans[r+1][c] = ans[r][c] = bone;
            dfs(r,c+1);
            ans[r+1][c] = ans[r][c] = 0;
            used[bone] = 0;
         }
    }

}

int main()
{
  //  freopen("in.txt","r",stdin);
   // freopen("my.txt","w",stdout);
    for(int h = 0,c = 0; h < 7; h++)
    for(int i = h; i < 7; i++){
        pip[i][h] = pip[h][i] = ++c;
    }
    int *layout = *tab;
    int cas = 0;
    while(~scanf("%d",layout)){
        if(cas) printf("


");
        memset(ans,0,sizeof(ans));
        memset(used,0,sizeof(used));
        cnt = 0;
        for(int i = 0; i < 7; i++) ans[i][8] = 233;
        for(int i = 0; i < 8; i++) ans[7][i] = 233;

        for(int i = 1; i < MAXD; i++)
            scanf("%d",layout+i);
        printf("Layout #%d:

",++cas);
        for(int i = 0; i < 7; i ++){
            for(int j = 0; j < 8; j++)
                printf("%4d",tab[i][j]);
            putchar('
');
        }
        printf("
Maps resulting from layout #%d are:

",cas);
        dfs(0,0);
        printf("There are %d solution(s) for layout #%d.
",cnt,cas);
    }

    return 0;
}