题目#

小葱将买来的糖放进了冰箱冷藏，但是小葱想吃糖了，小葱希望把自己想吃的糖从冰箱里面拿出来。具体来说，在一张 $N$ 行 $N$ 列的方格图中，有若干颗糖，每颗糖都是横向或者竖向摆放的。对于一个横向摆放的糖，我们只能左右移动这颗糖（任意距离，但不能跨越其他糖），而对于一个竖向摆放的糖只能上下移动。我们的目标是把编号为 $1$ 的糖从冰箱移出去，而移出去的方法是让该糖果能够移动到方格图的右边界的位置（只有一号糖果能移出去，其他糖即使在边界也不能出去）。我们保证任何一颗糖果长度至少为 $2$ ，并且 $1$ 号糖果一定横向放置。在糖果移动过程中不能穿越其他糖果，问在上述限制条件下小葱最少要移动多少次才能把 $1$ 号糖果移出冰箱。如果 $1$ 号糖果一开始就在右边界上请输出 $0$ 。

对于 $100\%$ 的数据， $1\leq N\leq8$ ，最多有 $13$ 种不同的糖果，答案不超过 $10$ 步。

题解#

*搜索！*搜索！搜索！

每次移动任意糖任意步，把每一个状态存下来（为了判断是否重复），然后bfs

如何存呢？其实一个糖只需要记录它的一个坐标位置，另一个是不变的。

对于这些糖的坐标，可以用一个 $n$ 进制数来存，最多有 $13$ 种不同的糖果，所以 $n^{13} - 1$ 就够了，算一下，unsigned long long够了

注意#

每次放入一个新的状态前先检测要放入的这个状态是不是答案，否则有可能会被卡超时（因为这个调了2个小时QAQ）

代码#

1
#include<bits/stdc++.h>
2
#define ull unsigned long long
3
#define DOWN 1
4
#define RIGHT 0
5

6
using namespace std;
7

8
const int N = 10;
9
int a[N][N], n, typenum;
10
const int M = 15;
11
// map压ull
12
map<ull, int> step;
13
queue<ull> qwq;
14
int towards[M], pos[M], len[M], another_pos[M];
15

16
void trans(ull state)
17
{
18
  int cnt = typenum;
19
  while(cnt >= 1)
20
  {
21
    ull b = state % n;
22
    pos[cnt] = b;
23
    state /= n;
24
    if(towards[cnt] == DOWN)
25
    {
26
//      cout << cnt << "点 DOWN" << endl;
27
      for(int i = b;i <= b + len[cnt] - 1;i++)
28
      {
29
        a[i][another_pos[cnt]] = cnt;
30
      }
31
    }
32
    else
33
    {
34
//      cout << cnt << "点 RIGHT" << endl;
35
      for(int i = b;i <= b + len[cnt] - 1;i++)
36
      {
37
        a[another_pos[cnt]][i] = cnt;
38
      }
39
    }
40
    cnt --;
41
  }
42
}
43

44
ull pack()
45
{
46
  ull start = 0;
47
  for(int i = 1;i <= typenum;i++)
48
  {
49
    start = start * n + pos[i];
50
  }
51
  return start;
52
}
53

54
int main()
55
{
56
  freopen("take.in", "r", stdin);
57
        freopen("take.out", "w", stdout);
58
  ios::sync_with_stdio(0), cin.tie(0);
59
  cin >> n;
60
  for(int i = 1;i <= n;i++)
61
  {
62
    for(int j = 1;j <= n;j++)
63
    {
64
      cin >> a[i][j];
65
    }
66
  }
67

68
  for(int i = 1;i <= n;i++)
69
  {
70
    for(int j = 1;j <= n;j++)
71
    {
72
      if(a[i][j] == 0) continue;
73
      int cl = a[i][j];
74
      if(a[i + 1][j] == cl) towards[cl] = DOWN;
75
      else towards[cl] = RIGHT;
76

77
      if(towards[cl] == DOWN) pos[cl] = i, another_pos[cl] = j;
78
      else pos[cl] = j, another_pos[cl] = i;
79

80
      int x = i, y = j;
81
      len[cl] = 0;
82
      while(x <= n && y <= n && a[x][y] == cl)
83
      {
84
        a[x][y] = 0;
85
        (towards[cl] == DOWN) ? (x ++) : (y++) ;
86
        len[cl] ++;
87
      }
88
      typenum = max(typenum, cl);
89
    }
90
  }
91
  ull start = 0;
92
  for(int i = 1;i <= typenum;i++)
93
  {
94
    start = start * n + pos[i];
95
  }
96
  step[start] = 0;
97
  qwq.push(start);
98

99
  while(qwq.size())
100
  {
101
    ull t = qwq.front();
102
    qwq.pop();
103
    memset(a, 0, sizeof a);
104
    trans(t);
105
    if(pos[1] + len[1] - 1 >= n)
106
    {
107
      cout << step[t] << endl;
108
      exit(0);
109
    }
110
    for(int i = 1;i <= typenum;i++)
111
    {
112
      if(towards[i] == DOWN)
113
      {
114
        for(int movement = 1;movement <= n;movement++)
115
        {
116
          if(a[pos[i] + len[i] - 1 + movement][another_pos[i]] != 0 || pos[i] + len[i] - 1 + movement > n) break;
117
          pos[i] = pos[i] + movement;
118
          ull now = pack();
119
          pos[i] -= movement;
120
          if(step[now] != 0)
121
            continue;
122
          qwq.push(now), step[now] = step[t] + 1;
123
          /*就这里*/if(i == 1 && pos[i] + len[i] - 1 + movement == n)
124
          {
125
            cout << step[now];
126
            exit(0);
127
          }
128
        }
129

130
        for(int movement = -1;movement >= -n;movement--)
131
        {
132
          if(a[pos[i] + movement][another_pos[i]] != 0 || pos[i] + movement < 1) break;
133
          pos[i] = pos[i] + movement;
134
          ull now = pack();
135
          pos[i] -= movement;
136
          if(step[now] != 0)
137
            continue;
138
          qwq.push(now), step[now] = step[t] + 1;
139
          if(i == 1 && pos[i] + len[i] - 1 + movement == n)
140
          {
141
            cout << step[now];
142
            exit(0);
143
          }
144
        }
145
      }
146
      else
147
      {
148
        for(int movement = 1;movement <= n;movement++)
149
        {
150
          if(a[another_pos[i]][pos[i] + len[i] - 1 + movement] != 0 || pos[i] + len[i] - 1 + movement > n) break;
151
          pos[i] = pos[i] + movement;
152
          ull now = pack();
153
          pos[i] -= movement;
154
          if(step[now] != 0)
155
            continue;
156
          qwq.push(now), step[now] = step[t] + 1;
157
          if(i == 1 && pos[i] + len[i] - 1 + movement == n)
158
          {
159
            cout << step[now];
160
            exit(0);
161
          }
162
        }
163

164
        for(int movement = -1;movement >= -n;movement--)
165
        {
166
          if(a[another_pos[i]][pos[i] + movement] != 0 || pos[i] + movement < 1) break;
167
          pos[i] = pos[i] + movement;
168
          ull now = pack();
169
          pos[i] -= movement;
170
          if(step[now] != 0)
171
            continue;
172
          qwq.push(now), step[now] = step[t] + 1;
173
          if(i == 1 && pos[i] + len[i] - 1 + movement == n)
174
          {
175
            cout << step[now];
176
            exit(0);
177
          }
178
        }
179
      }
180
    }
181
    //step等由这个点向外扩展的时候再更新
182
  }
183

184
  return 0;
185
}

小葱拿糖

https://blog.histcat.top/posts/taking-candies/

作者

Histcat

发布于

2023-10-02

许可协议

CC BY-NC-SA 4.0

大数翻倍法求（拓展）中国剩余定理

Mexor