习题 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;
}