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

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

#include<bits/stdc++.h>

const int MAXD = ;
const int MAXB = ;
const int MAXP = ; bool used[MAXB];// used Bone
int pip[MAXP][MAXP];// pip 2 Bone int tab[][];
int ans[][]; int cnt;
void dfs(int r,int c)
{
while(ans[r][c]) {
if(c == ) { r++; c = -; }
c++;
}
if(r == ) {
for(int i = ; i < ; i++){
for(int j = ; j < ; j++){
printf("%4d",ans[i][j]);
}
putchar('\n');
}
putchar('\n');
cnt++;
return ;
} int &p0 = tab[r][c];
if(!ans[r][c+]){ // 横着放
int &p1 = tab[r][c+];
int &bone = pip[p0][p1];
if(!used[bone]){
used[bone] = ;
ans[r][c+] = ans[r][c] = bone;
dfs(r,c+);
ans[r][c+] = ans[r][c] = ;
used[bone] = ;
}
} if(!ans[r+][c]) { //竖着放
int &p2 = tab[r+][c];
int &bone = pip[p0][p2];
if(!used[bone]){
used[bone] = ;
ans[r+][c] = ans[r][c] = bone;
dfs(r,c+);
ans[r+][c] = ans[r][c] = ;
used[bone] = ;
}
} } int main()
{
// freopen("in.txt","r",stdin);
// freopen("my.txt","w",stdout);
for(int h = ,c = ; h < ; h++)
for(int i = h; i < ; i++){
pip[i][h] = pip[h][i] = ++c;
}
int *layout = *tab;
int cas = ;
while(~scanf("%d",layout)){
if(cas) printf("\n\n\n");
memset(ans,,sizeof(ans));
memset(used,,sizeof(used));
cnt = ;
for(int i = ; i < ; i++) ans[i][] = ;
for(int i = ; i < ; i++) ans[][i] = ; for(int i = ; i < MAXD; i++)
scanf("%d",layout+i);
printf("Layout #%d:\n\n",++cas);
for(int i = ; i < ; i ++){
for(int j = ; j < ; j++)
printf("%4d",tab[i][j]);
putchar('\n');
}
printf("\nMaps resulting from layout #%d are:\n\n",cas);
dfs(,);
printf("There are %d solution(s) for layout #%d.\n",cnt,cas);
} return ;
}
05-26 02:01