P1312. Mayan 游戏

发表于 分类于 阅读次数： Waline： 本文字数： 656 阅读时长 ≈ 2 分钟

考点

  • DFS
  • 剪枝

题解

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
118
#include <bits/stdc++.h>
using namespace std;
const int maxn = 20;
int N;
bool v[maxn][maxn];
int g[maxn][maxn], backup_g[maxn][maxn][maxn];  // 当前布局和布局备份
int cnt[maxn], backup_cnt[maxn][maxn];  // 当前每个方块个数和个数备份

// 保存结果
struct node {
  int x_, y_, dir_;
} ans[maxn];

void backup(int now) {
  memcpy(backup_g[now], g, sizeof(g));
  memcpy(backup_cnt[now], cnt, sizeof(cnt));
}

void recover(int now) {
  memcpy(g, backup_g[now], sizeof(backup_g[now]));
  memcpy(cnt, backup_cnt[now], sizeof(backup_cnt[now]));
}

void f(int x, int y, int dir) {
  swap(g[x][y], g[x + dir][y]);
  while (1) {
    bool flag = 1;
    memset(v, 0, sizeof(v));
    // 处理悬空
    for (int x = 0; x < 5; ++x) {
      int t = 0;
      for (int y = 0; y < 7; ++y) {
        if (g[x][y]) g[x][t++] = g[x][y];
      }
      while (t < 7) g[x][t++] = 0;
    }
    // 消消乐
    for (int x = 0; x < 5; ++x) {
      for (int y = 0; y < 7; ++y) {
        if (!g[x][y]) continue;
        int l = x, r = x;
        // 左右找
        while (l - 1 >= 0 && g[l - 1][y] == g[x][y]) --l;
        while (r + 1 < 5 && g[r + 1][y] == g[x][y]) ++r;
        if (r - l + 1 >= 3) {
          v[x][y] = 1;
          flag = 0;
        } else {
          // 上下找
          l = y, r = y;
          while (l - 1 >= 0 && g[x][l - 1] == g[x][y]) --l;
          while (r + 1 < 7 && g[x][r + 1] == g[x][y]) ++r;
          if (r - l + 1 >= 3) {
            v[x][y] = 1;
            flag = 0;
          }
        }
      }
    }
    if (flag) return;
    // 删除消掉的
    for (int x = 0; x < 5; ++x) {
      for (int y = 0; y < 7; ++y) {
        if (v[x][y]) --cnt[g[x][y]], ++cnt[0], g[x][y] = 0;
      }
    }
  }
}

bool dfs(int now) {
  if (now == N) return (cnt[0] == 35);
  // 可行性剪枝：只剩1个或2个肯定不能被消掉
  for (int i = 1; i <= 10; ++i) {
    if (cnt[i] == 1 || cnt[i] == 2) return 0;
  }
  backup(now);
  for (int x = 0; x < 5; ++x) {
    for (int y = 0; y < 7; ++y) {
      if (!g[x][y]) continue;
      // 向右移动
      if (x + 1 < 5) {
        ans[now] = {x, y, 1};
        f(x, y, 1);
        if (dfs(now + 1)) return 1;
        recover(now);
      }
      // 向左移动
      // 最优性剪枝：左边没东西才向左走
      if (x - 1 >= 0 && !g[x - 1][y]) {
        ans[now] = {x, y, -1};
        f(x, y, -1);
        if (dfs(now + 1)) return 1;
        recover(now);
      }
    }
  }
  return 0;
}

int main() {
  cin >> N;
  cnt[0] = 35;
  for (int t, y, x = 0; x < 5; ++x) {
    y = 0;
    while (cin >> t && t) {
      ++cnt[t], --cnt[0];
      g[x][y++] = t;
    }
  }
  if (dfs(0)) {
    for (int i = 0; i < N; ++i) {
      cout << ans[i].x_ << " " << ans[i].y_ << " " << ans[i].dir_ << endl;
    }
  } else {
    cout << "-1" << endl;
  }
  return 0;
}

思路

搜索顺序：依次枚举每一步选择哪个方块，向左右哪个方向移动。

等效性剪枝：

  1. 左侧没方块才向左走，因为当前方块向左走和左侧方块向右走是等价的，没必要重复。
  2. 就算右侧方块和当前方块相同，也不能剪枝！因为题目要求恰好n步，有时候需要多余步数充数。

可行性剪枝：

  1. 如果某方块只剩1或2块了，直接剪枝。

消消乐大模拟直接看代码注释即可。