poj-2044 Weather Forecast

发表于 分类于 阅读次数： Waline： 本文字数： 592 阅读时长 ≈ 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
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 366;
// 0-4上下左右不变
const int dx[5] = {-1, 1, 0, 0, 0}, dy[5] = {0, 0, -1, 1, 0};
int n;
// s[i][x][y]：第i天(x,y)是否出行
int s[maxn][4][4];
bool v[maxn][4][4][8][8][8][8];

struct node {
  // 第几天，2*2方格左上角的坐标，左上右上左下右下四个角（连续几天没下雨）
  int day_, x_, y_, s0_, s1_, s2_, s3_;
  node(int day = 0, int x = 0, int y = 0, int s0 = 0, int s1 = 0, int s2 = 0,
       int s3 = 0)
      : day_(day), x_(x), y_(y), s0_(s0), s1_(s1), s2_(s2), s3_(s3) {}
};

bool valid(int x, int y) { return x >= 0 && y >= 0 && x < 3 && y < 3; }

int bfs() {
  // 初始化状态
  memset(v, 0, sizeof(v));
  // 第一天不符合要求
  if (s[1][1][1] || s[1][1][2] || s[1][2][1] || s[1][2][2]) return 0;
  queue<node> q;
  q.push(node(1, 1, 1, 1, 1, 1, 1));
  v[1][1][1][1][1][1][1] = 1;
  while (!q.empty()) {
    node u = q.front();
    q.pop();
    if (u.day_ == n) return 1;
    for (int i = 0; i < 5; ++i) {
      for (int j = 1; j <= 2; ++j) {
        int day = u.day_ + 1, x = u.x_ + j * dx[i], y = u.y_ + j * dy[i];
        int s0 = u.s0_, s1 = u.s1_, s2 = u.s2_, s3 = u.s3_;
        if (!valid(x, y)) continue;
        // 新位置不符合要求
        if (s[day][x][y] || s[day][x + 1][y] || s[day][x][y + 1] ||
            s[day][x + 1][y + 1])
          continue;
        // 判断四个角，是否存在连续七天没下雨
        if (!x && !y)
          s0 = 0;
        else if (++s0 == 7)
          continue;
        if (!x && y == 2)
          s1 = 0;
        else if (++s1 == 7)
          continue;
        if (x == 2 && !y)
          s2 = 0;
        else if (++s2 == 7)
          continue;
        if (x == 2 && y == 2)
          s3 = 0;
        else if (++s3 == 7)
          continue;
        if (v[day][x][y][s0][s1][s2][s3]) continue;
        q.push(node(day, x, y, s0, s1, s2, s3));
        v[day][x][y][s0][s1][s2][s3] = 1;
      }
    }
  }
  return 0;
}

int main() {
  while (cin >> n && n) {
    for (int i = 1; i <= n; ++i) {
      for (int x = 0; x < 4; ++x) {
        for (int y = 0; y < 4; ++y) {
          cin >> s[i][x][y];
        }
      }
    }
    cout << bfs() << endl;
  }
  return 0;
}

思路

本题最大的难点，在于如何判断全图是否有连续7天没下雨的地方；

可能你想每个状态都直接保存一个图，我也尝试过，然后MLE了。

实际上只需要记录左上s0，右上s1，左下s2，右下s3四个角的连续不下雨天数即可，

因为我们的方块是2*2的，只要上面某个角下过雨，那么该角所在的2*2格子就不会连续干旱。

所以用(天数, 云左上角的x, 云左上角的y, s0, s1, s2, s3)来表达状态即可。