POJ-1324 Holedox Moving 解题报告

题意简述
¶

在一个 $N \times M$ 的矩形方格地图中，有一条长度为 $L$ 的贪吃蛇。地图的 $(1, 1)$ 位置是一个出口，如果贪吃蛇能移动到出口，输出最短步数（头到达出口的步数）；否则输出 $- 1$ 。

贪吃蛇的移动规则如下：

只能朝边相邻的格子移动
不能朝障碍物移动（身体及四周墙壁都视作障碍物）

数据范围： $1 ⩽ N, M ⩽ 8$ ， $2 ⩽ L ⩽ 8$ 。

题目简析
¶

为方便叙述，对贪吃蛇的身体进行编号：蛇头为 $- 1$ 号，蛇尾为 $L - 2$ 号，以此类推。因为贪吃蛇的身体是紧邻的。所以，当我们确定了蛇头的位置，对于身体的其它任一部分 $i$ ，我们仅需知道 $i$ 相对与 $i - 1$ 的方向即可。于是可用链表的思想来存储贪吃蛇：

蛇头用一个二元组 $(x, y)$ 表示其位置
身体其它部分 $i$ 用一个整数 $d i r (i) \in {0, 1, 2, 3}$ 来表示它相对 $i - 1$ 的方向。

注意到方向只有 $4$ 个数，且蛇的长度 $L ⩽ 8$ 。不难想到状态压缩，则用一个 $28$ 位 bit 的整数表示蛇身就够了：

约定第 $2 i, 2 i + 1$ 两位 bit 表示蛇身第 $i$ 号部分相对于 $i - 1$ 号部分的方向。
当蛇头朝某一合法位置移动后， $d i r^{'} (i) = \frac{d i r (i - 1)}{4} \times 4 = c$ 其中， $d i r^{'}$ 表示移动后的蛇身位置关系， $c$ 为此次蛇头移动的方向 ^[1]。

所以，当贪吃蛇移动一步后，我们仅需将方向变量：左移两位，再右移两位，再或上蛇头移动的方向。剩下的问题就是宽度优先搜索了。

TIP

问题的难点在于记录移动的状态。

复杂度分析
¶

由于移动操作仅需 $O (1)$ 就可以完成了；但是，判断下一步是否为蛇的身体将需要 $O (L)$ 的时间完成。一共有 $O (N \times M \times 2^{2 L - 2})$ 个状态。

空间复杂度 $O (N \times M \times 2^{2 L - 2})$
时间复杂度 $O (N \times M \times L \times 2^{2 L - 2})$

AC 代码：

poj.1324.cpp | 96 lines.

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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

const int nx[] = { -1, 0, 1, 0 };
const int ny[] = { 0, 1, 0, -1 };

int T_T, N, M, L, B, bit, sx, sy, sd;
bool vis[21][21][1 << 14 | 1], blank[21][21];

struct node {
  int x, y, d, s;
  node(int x = 0, int y = 0, int d = 0, int s = 0) : x(x), y(y), d(d), s(s) {
  }
  bool block(int x, int y) {
    if (x >= 1 && y >= 1 && x <= N && y <= M && blank[x][y]) {
      int mx = this->x;
      int my = this->y;
      int md = this->d;
      for (int i = 1; i < L; ++i) {
        int d = md & 3;
        mx += nx[d];
        my += ny[d];
        md >>= 2;
        if (mx == x && my == y) return true;
      }
      return false;
    }
    return true;
  }
};

queue<node> Q;

int bfs() {
  while (!Q.empty()) Q.pop();
  Q.push(node(sx, sy, sd));
  vis[sx][sy][sd] = true;

  while (!Q.empty()) {
    node now = Q.front();
    Q.pop();

    if (now.x == 1 && now.y == 1) return now.s;
    for (int d = 0; d < 4; ++d) {
      int mx = now.x + nx[d];
      int my = now.y + ny[d];
      if (!now.block(mx, my)) {
        int md = ((now.d << 2) & bit) | (d ^ 2);
        if (vis[mx][my][md]) continue;
        vis[mx][my][md] = true;
        Q.push(node(mx, my, md, now.s + 1));
      }
    }
  }

  return -1;
}

void work() {
  while (scanf("%d%d%d", &N, &M, &L) == 3 && N && M && L) {
    bit = (1 << (L - 1 << 1)) - 1;
    for (int n = 1; n <= N; ++n)
      for (int m = 1; m <= M; ++m) memset(vis[n][m], 0, bit + 1);
    memset(blank, 1, sizeof blank);

    scanf("%d%d", &sx, &sy);
    sd = 0;
    int mx = sx, my = sy, mu, mv;
    for (int i = 0; i < L - 1; ++i) {
      scanf("%d%d", &mu, &mv);
      for (int d = 0; d < 4; ++d)
        if (mx + nx[d] == mu && my + ny[d] == mv) {
          sd |= d << (i << 1);
          mx = mu;
          my = mv;
          break;
        }
    }
    scanf("%d", &B);
    while (B--) {
      scanf("%d%d", &mu, &mv);
      blank[mu][mv] = false;
    }

    printf("Case %d: %d\n", ++T_T, bfs());
  }
}

int main() {
  work();
  return 0;
}

题意简述¶

题目简析¶

复杂度分析¶

Related¶

题意简述
¶

题目简析
¶

复杂度分析
¶

Related
¶