UVA 211 The Domino Effect

uva dfs

就是 dfs. 由左上到右下. 一行一行地走.
要小心輸出格式, 我把 There are %d solution(s) for layout 那一句在 uDebug 比較了很久, 明明是一樣的句子, 但他就是顯示不同, 最後用他的句子就過了. 可能是多了一些奇怪字元.

uva211.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;

const int MAXX = 8; // 0 - 7
const int MAXY = 7; // 0 - 6


int dominoes[7][7];
int input[10][10];
int curState[10][10];
bool used[29];
int solutionCount;

void build_dominoes() {
  int cardno = 1;
  for(int i = 0; i <= 6; ++i)
    for(int j = i; j <= 6; ++j)
      dominoes[i][j] = dominoes[j][i] = cardno++;
}

bool validXY(int x, int y) {
  return x >= 0 && x < MAXX
      && y >= 0 && y < MAXY;
}

void print_matrix(int input[][10]) {
  for(int i = 0; i < 7; ++i) {
    for(int j = 0; j < 8; ++j)
      printf("%4d", input[j][i]);
    printf("\n");
  }
  printf("\n");
}

void dfs(int curX, int curY ) {
  if(curX == MAXX - 1 && curY == MAXY - 1 && curState[curX][curY] != -1) {
    print_matrix(curState);
    solutionCount++;
    return;
  }

  int nextX = (curX + 1)%MAXX;
  int nextY = curY + (curX + 1)/MAXX;
  int vc = input[curX][curY];
  int vh = input[curX+1][curY];
  int vv = input[curX][curY+1];

  if(curState[curX][curY] != -1) {
    if(validXY(nextX, nextY))
      dfs(nextX, nextY);
    return;
  } else {
    if(validXY(curX+1, curY)) {
      if(curState[curX+1][curY] == -1) {
        int cardno = dominoes[vc][vh];
        if(!used[cardno]) {
          used[cardno] = true;
          curState[curX][curY] = curState[curX+1][curY] = cardno;
          dfs(nextX, nextY);
          curState[curX][curY] = curState[curX+1][curY] = -1;
          used[cardno] = false;
        }
      }
    }
    if(validXY(curX, curY+1)) {
      if(curState[curX][curY+1] == -1) {
        int cardno = dominoes[vc][vv];
        if(!used[cardno]) {
          used[cardno] = true;
          curState[curX][curY] = curState[curX][curY+1] = cardno;
          dfs(nextX, nextY);
          curState[curX][curY] = curState[curX][curY+1] = -1;
          used[cardno] = false;
        }
      }
    }
  }

}

bool readline(int ylevel) {
  for(int i = 0; i < 8; ++i)
    if(scanf("%d", &input[i][ylevel]) == EOF)
      return false;
  return true;
}


int main() {
  build_dominoes();

  int ncase = 0;
  while(readline(0)) {
    for(int i = 1; i < 7; ++i)
      readline(i);

    ncase++;
    solutionCount = 0;
    memset(curState, -1, sizeof(curState));
    memset(used, false, sizeof(used));

    if(ncase != 1)
      printf("\n\n\n");
    printf("Layout #%d:\n\n", ncase);
    print_matrix(input);

    printf("\nMaps resulting from layout #%d are:\n\n", ncase);
    dfs(0, 0);
    printf("\nThere are %d solution(s) for layout #%d.\n", solutionCount, ncase);
  }

  return 0;
}