AcWing 191. 天气预报 (dfs + 记忆化搜索 + dp)

这道题有个很重要的性质:

只要四个角落在7天之内有下雨,那么就是合法的.

接下来我们以中间的坐标开始往四边搜索,如果能熬过第n天,那么就输出1,否则输出0.这题用深搜和宽搜都可以.但是暴力搜索时间复杂度太大了,我们需要一些优化,于是我们使用记忆化搜索,也就是dp,我们用,表示当前是第day天,云在(x, y)的时候,左上,左下,右上,右下角距离上次下雨的天数.

#include <bits/stdc++.h>
// #define LOCAL
#define INF 0x3f3f3f3f3f3f3f3f
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define debug(a) cout << #a << "=" << a << endl;
using namespace std;
const int N = 367, M = 2807;
const int dx[] = {1, -1, 2, -2, 0, 0, 0, 0, 0}, dy[] = {0, 0, 0, 0, 1, -1, 2, -2, 0};
int n;
int state[N];
struct rec{
    int d[5];
}bg;
bool vis[N][5][5][M];
void init(){
    memset(state, 0, sizeof state);
    memset(bg.d, 0, sizeof bg.d);
    memset(vis, 0, sizeof vis);
}

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

int Get(int x, int y){
    return 1 << (x * 4 + y);
}

bool check(int day, int x, int y, rec rc){
    //先判断四个角距离上次下雨是否超过6天
    for (int i = 0; i < 4; ++i)
        if (day - rc.d[i] > 6)
            return false;
    //判断是否满足不该下雨就不下雨
    int weather = Get(x, y) | Get(x + 1, y) | Get(x, y + 1) | Get(x + 1, y + 1);
    if (weather & state[day])
        return false;
    //判断当前的状态是否访问过,如果访问过那么必定是经历过回溯的,说明当前的状态不行.
    int base = 8, s = 0;
    for (int i = 0; i < 4; ++i)
        s = s * base + (day - rc.d[i]);
    if (vis[day][x][y][s])
        return false;
    return vis[day][x][y][s] = true;
}
bool dfs(int day, int x, int y, rec rc){
    if (!check(day, x, y, rc))
        return false;
    if (day == n)
        return true;
    for (int i = 0; i < 9; ++i){
        int nowx = x + dx[i], nowy = y + dy[i];
        if (!is_valid(nowx, nowy))
            continue;
        rec nowrc = rc;
        if (nowx == 0 && nowy == 0)
            nowrc.d[0] = day + 1;
        if (nowx == 0 && nowy == 2)
            nowrc.d[1] = day + 1;
        if (nowx == 2 && nowy == 0)
            nowrc.d[2] = day + 1;
        if (nowx == 2 && nowy == 2)
            nowrc.d[3] = day + 1;
        if (dfs(day + 1, nowx, nowy, nowrc))
            return true;
    }
    return false;
}

void solve(){
    init();
    for (int i = 1, x; i <= n; ++i)
        for (int j = 0; j < 16; ++j){
            cin >> x;
            state[i] |= (1 << j) * x;
        }
    cout << dfs(1, 1, 1, bg) << 
;
}

signed main(){
#ifdef LOCAL
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    IOS;
    while (cin >> n, n)
        solve();
}