poj-3322 Bloxorz I

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

考点

  • BFS

题解

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
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 5e2 + 50;
// lie=0,长方体立在(x,y)
// lie=1,长方体的左半部分在(x,y)
// lie=2,长方体的上半部分在(x,y)
struct node {
  int x_, y_, lie_;
  node(int x = 0, int y = 0, int lie = 0) : x_(x), y_(y), lie_(lie) {}
};
// 0~3左右上下的方向数组
const int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
// nxt_x[i][j]表示lie=i时，朝方向j滚动x的变化
const int nxt_x[3][4] = {{0, 0, -2, 1}, {0, 0, -1, 1}, {0, 0, -1, 2}};
// nxt_y[i][j]表示lie=i时，朝方向j滚动y的变化
const int nxt_y[3][4] = {{-2, 1, 0, 0}, {-1, 2, 0, 0}, {-1, 1, 0, 0}};
// nxt_lie[i][j]表示lie=i时，朝方向j滚动后lie的新值
const int nxt_lie[3][4] = {{1, 1, 2, 2}, {0, 0, 1, 1}, {2, 2, 0, 0}};
int r, c, steps[maxn][maxn][3];
queue<node> q;
char mp[maxn][maxn];
node bg, ed;

bool valid(int x, int y) { return x >= 1 && x <= r && y >= 1 && y <= c; }

bool valid(node x) {
  if (!valid(x.x_, x.y_)) return 0;
  if (mp[x.x_][x.y_] == '#') return 0;
  if (x.lie_ == 0 && mp[x.x_][x.y_] != '.') return 0;
  if (x.lie_ == 1 && mp[x.x_][x.y_ + 1] == '#') return 0;
  if (x.lie_ == 2 && mp[x.x_ + 1][x.y_] == '#') return 0;
  return 1;
}

// 处理起点和终点
void init() {
  for (int i = 1; i <= r; ++i) {
    for (int j = 1; j <= c; ++j) {
      if (mp[i][j] == 'O') {
        bg = node(i, j, 0), mp[i][j] = '.';
      } else if (mp[i][j] == 'X') {
        for (int k = 0; k < 4; ++k) {
          int x = i + dx[k], y = j + dy[k];
          if (valid(x, y) && mp[x][y] == 'X') {
            ed.x_ = min(x, i), ed.y_ = min(y, j);
            ed.lie_ = k < 2 ? 1 : 2;
            mp[i][j] = mp[x][y] = '.';
            break;
          }
        }
        if (mp[i][j] == 'X') ed = node(i, j, 0), mp[i][j] = '.';
      }
    }
  }
}

int bfs() {
  while (!q.empty()) q.pop();
  steps[bg.x_][bg.y_][bg.lie_] = 0, q.push(bg);
  while (!q.empty()) {
    node u = q.front();
    q.pop();
    for (int i = 0; i < 4; ++i) {
      node nxt;
      nxt.x_ = u.x_ + nxt_x[u.lie_][i];
      nxt.y_ = u.y_ + nxt_y[u.lie_][i];
      nxt.lie_ = nxt_lie[u.lie_][i];
      if (!valid(nxt)) continue;
      if (~steps[nxt.x_][nxt.y_][nxt.lie_]) continue;
      steps[nxt.x_][nxt.y_][nxt.lie_] = steps[u.x_][u.y_][u.lie_] + 1;
      if (nxt.x_ == ed.x_ && nxt.y_ == ed.y_ && nxt.lie_ == ed.lie_)
        return steps[nxt.x_][nxt.y_][nxt.lie_];
      q.push(nxt);
    }
  }
  return -1;
}

int main() {
  while (cin >> r >> c && r && c) {
    memset(steps, -1, sizeof(steps));
    for (int i = 1; i <= r; ++i) scanf("%s", mp[i] + 1);
    init();
    int res = bfs();
    ~res ? cout << res : cout << "Impossible";
    cout << endl;
  }
  return 0;
}

思路

用一个三元组(x, y, lie)代表一个状态（搜索树中的一个节点），其中：

  • lie = 0表示长方体立在(x, y)
  • lie = 1表示长方体横向躺着，左半部分位置在(x, y)
  • lie = 2表示长方体纵向躺着，上半部分在(x, y)

数组steps[x][y][lie]记录从起始状态到达每个状态的最小步数

其余细节见代码即可