习题 7-3 uva211
题意：给你28个多米勒牌，要求刚好铺满一个7x8的图，输出所有答
案。每个牌只能使用一次
思路：
对每个位置分别搜索其右边 和 下边。
但是在中途，细节上有点问题。最开始想的是搜到最后一个点输出答案，但总是有问题。然后搜索部分换了个姿势，记录以使用的牌数，终于AC。感觉 - -自己好坑
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
typedef long long ll;
using namespace std;
const int inf = 0x3f3f3f3f;
int all;
int vis[10][10];
int ans[10][10];
int p[10][10];
int pip[10][10];
int vis_pip[30][30];
int dir[2][2] = {{0,1},{1,0}};
void ini()
{
int tt = 1;
for(int i = 0; i < 7; i++)
for(int j = i; j < 7; j++)
{
pip[i][j] = pip[j][i] = tt++;
}
return;
}
void dfs(int cur,int num)
{
int x = cur/8;
int y = cur%8;
if(num == 28) //搜满28个
{
for(int i = 0; i < 7; i++)
{
for(int j = 0; j < 8; j++)
{
printf("%4d",ans[i][j]);
}
printf("
");
}
all ++;
printf("
");
return ;
}
if(vis[x][y])
{
dfs(cur+1,num);
return ;
}
if(x > 6 || y > 7)
return ;
for(int i = 0;i < 2;i++)
{
if(i == 0 && y == 7) continue;
if(i == 1 && x == 6) continue;
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(vis[tx][ty] || vis_pip[p[x][y]][p[tx][ty]])
continue;
vis[x][y] = vis[tx][ty]= vis_pip[p[x][y]][p[tx][ty]] = vis_pip[p[tx][ty]][p[x][y]] = 1;
ans[x][y] = ans[tx][ty] = pip[p[x][y]][p[tx][ty]];
dfs(cur+1,num+1);
vis[x][y] = vis[tx][ty]= vis_pip[p[x][y]][p[tx][ty]] = vis_pip[p[tx][ty]][p[x][y]] = 0;
}
return ;
}
int main()
{
int cas = 1;
ini();
// freopen("in.txt","r",stdin);
while(scanf("%d%d%d%d%d%d%d%d",&p[0][0],&p[0][1],&p[0][2],&p[0][3],&p[0][4],&p[0][5],&p[0][6],&p[0][7]) != EOF)
{
for(int i = 1; i < 7; i++)
for(int j = 0; j < 8; j++)
{
scanf("%d",&p[i][j]);
}
if(cas!= 1)
printf("
");
memset(vis,0,sizeof(vis));
memset(vis_pip,0,sizeof(vis_pip));
printf("Layout #%d:
",cas);
for(int i = 0; i < 7; i++)
{
for(int j = 0; j <8; j++)
{
printf("%4d",p[i][j]);
}
printf("
");
}
printf("
");
printf("Maps resulting from layout #%d are:
",cas);
all = 0;
dfs(0,0);
printf("There are %d solution(s) for layout #%d.
",all,cas++);
}
return 0;
}