UVa 211 The Domino Effect 多米诺效应 暴力搜索

题目链接：UVa 211 The Domino Effect
题目描述：

一张多米诺骨牌拥有两个数值，一共有二十八张不同的多米诺骨牌，这二十八张多米诺骨牌的点数如下图所示：

上图的$Bone$代表编号，而$Pips$代表两个数值。现在输入给定$7$行$8$列数据，保证输入的数据一定是上述多米诺骨牌的牌值，你需要用上述$28$张（每张牌用且只用一次）多米诺骨牌（骨牌可以横着摆或者竖着摆）来还原这个输入数据，你需要输出所有可能的摆放方式。

题解：

这道题我们的想法是：每次选择两个没有组合的数字组成一张多米诺骨牌，要保证组合成的多米诺骨牌没有被其他地方的数字使用过，如果最后能够将所有的数字都进行组合，那么就得到了一种可能的答案。
那么如何搜索呢？可以从$(0,0)$位置开始进行搜索，每次搜索的时候我们尝试将当前位置和右边的数字或者下边的数字组成一张多米诺骨牌，然后下一次搜索的位置变为当前位置向右移动一个，当然这样进行搜索的话右边的左边的数字可能已经被使用过了，所以我们在右边坐标数字被使用过的情况下只需要再往右边进行搜索，知道右边的数字没有被使用或者当前已经到达最右边了，但是还是被使用了，那么我们直接到下一行进行搜索即可。那么这样搜索的深度是$58$并且每层最多有$2$个选择，这样似乎复杂度不允许我们通过。但是这样得到的一个搜索树是稀疏的，因为当某一个位置确定了之后随即就有另一个位置确定，那么搜索结点个数应该是不超过 2 29 2^{29} 229。
注意：这道题的输出格式比较复杂，最后一组的输出末尾应该只有一个换行，可以先参看输出格式。

代码：

#include <bits/stdc  .h>

const int NUM_DIRECTION = 2;
const int ROW_NUM = 7;
const int COLUMN_NUM = 8;

using namespace std;

int ansNum, caseID;
int ans[ROW_NUM][COLUMN_NUM], used[ROW_NUM * COLUMN_NUM   1], number[ROW_NUM][COLUMN_NUM], id[7][7];
int dx[] = {0, 1};
int dy[] = {1, 0};

bool getInput()
{
    for (int i = 0; i < ROW_NUM; i  ) {
        for (int j = 0; j < COLUMN_NUM; j  ) {
            if (!(cin >> number[i][j])) { return false; };
        }
    }
    return true;
}

void init()
{
    ansNum = 0;
    memset(ans, 0, sizeof(ans));
    memset(used, 0, sizeof(used));
}

void dfs(int x, int y, int nowDepth)
{
    if (nowDepth == ROW_NUM * COLUMN_NUM) {
        for (int i = 0; i < ROW_NUM; i  ) {
            for (int j = 0; j < COLUMN_NUM; j  ) {
                cout << setw(4) << ans[i][j];
            }
            cout << endl;
        }
        cout << endl << endl;
        ansNum  ;
        return;
    }
    if (y == COLUMN_NUM) {
        x  ;
        y = 0;
    }
    if (ans[x][y] != 0) {
        dfs(x, y   1, nowDepth   1);
        return;
    }
    for (int i = 0; i < NUM_DIRECTION; i  ) {
        int nx = x   dx[i];
        int ny = y   dy[i];
        if (nx >= ROW_NUM || ny >= COLUMN_NUM || ans[nx][ny] != 0 || used[id[number[x][y]][number[nx][ny]]]) { continue; }
        ans[x][y] = ans[nx][ny] = id[number[x][y]][number[nx][ny]];
        used[id[number[x][y]][number[nx][ny]]] = true;
        dfs(x, y   1,  nowDepth   1);
        ans[x][y] = ans[nx][ny] = 0;
        used[id[number[x][y]][number[nx][ny]]] = false;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int cnt = 1;
    for (int i = 0; i < 7; i  ) {
        for (int j = i; j < 7; j  ) {
            id[i][j] = id[j][i] = cnt  ; // 记录每种Domino的编号
        }
    }
    while (getInput()) {
        if (caseID) { cout << endl << endl << endl << endl << endl; }
        caseID  ;
        cout << "Layout #" << caseID << ":" << endl << endl << endl;
        for (int i = 0; i < ROW_NUM; i  ) {
            for (int j = 0; j < COLUMN_NUM; j  ) {
                cout << setw(4) << number[i][j];
            }
            cout << endl;
        }
        cout << endl << "Maps resulting from layout #" << caseID << " are:" << endl << endl << endl;
        init();
        dfs(0, 0, 0);
        cout << "There are " << ansNum << " solution(s) for layout #" << caseID << "." << endl;
    }
    return 0;
}

这篇好文章是转载于：学新通技术网