更多的测试数据
原题目链接

一眼丁真，鉴定为 搜索

用云左上方的点的坐标来代表云的坐标。显然，这个点位于 (1,1)(1,1) 到 (3,3)(3,3) 之间。

注意到，只需要考虑 (1,1)(1,1) (1,3)(1,3) (3,1)(3,1) (3,3)(3,3) 这四个点会不会七天以上淋不到雨就可以了，因为这是云朵在四个角落的情况，最没可能淋到雨。

但是最朴素的搜索是肯定会超时的，意味着我们需要考虑剪枝或记忆化。我们最朴素的搜索的问题往往是花费大量计算了不可能成为结果的情况 或 已经计算过了的情况。这道题中属于后者。我们最朴素的搜索计算了大量天数、云朵位置、四个角落上面未下雨的天数都相同 的情况。

因此考虑记忆化，用 bool vst[t][s][8][8][8][8] 数组，记录“第 $t$ 天，云朵在 $s$ 位置，(1,1),(1,3),(3,1),(3,3) 四个位置分别有多少天没有下雨”这种情况有没有被访问过，如果被访问过就不用再次计算了。因为一共才 $4 \times 4$ 宫格，所以有极高的概率重复，这种记忆化也就效率很高。

#include<bits/stdc++.h>
#define int long long
#define inf 0x7fffffffffffffff
using namespace std;

//#define cin is
//#define cout os
//ifstream is("weather.in", ios::in);
//ofstream os("weather.out", ios::out);

const int N = 400;
const int dx[9] = { 0,0,0,1,-1,0,0,2,-2 };
const int dy[9] = { 0,1,-1,0,0,2,-2,0,0 };
const int plt[12] = { 0,1,2,3,0,4,5,6,0,7,8,9 };

int T, day[N];
bool vst[N][10][8][8][8][8];
bool ans;

bool check(int t, int x, int y, int a[]) {
    int p[4] = { ((x - 1) * 4 + y),(x * 4 + y),((x - 1) * 4 + y + 1),(x * 4 + y + 1) };
    if (x < 1 || x>3 || y < 1 || y>3) {
        return 0;
    }
    for (int k = 1;k <= 4;++k) {
        if (a[k] >= 7) {
            return 0;
        }
    }
    for (int k = 0;k < 4;++k) {
        if ((1 << p[k]) & day[t]) {
            return 0;
        }
    }
    if (vst[t][plt[p[0]]][a[1]][a[2]][a[3]][a[4]]) {
        return 0;
    }
    return 1;
}
void dfs(int t, int x, int y, int a[]) {
    if (ans) {
        return;
    }
    if (t == T) {
        ans = 1;
        return;
    }
    int b[5];
    memset(b, 0, sizeof(b));
    for (int k = 0;k < 9;++k) {
        int nx = x + dx[k], ny = y + dy[k];
        if ((!t) && k) {
            break;
        }
        for (int j = 1;j <= 4;++j) {
            b[j] = a[j] + 1;
        }
        if (nx == 1 && ny == 1) {
            b[1] = 0;
        }
        if (nx == 1 && ny == 3) {
            b[2] = 0;
        }
        if (nx == 3 && ny == 1) {
            b[3] = 0;
        }
        if (nx == 3 && ny == 3) {
            b[4] = 0;
        }
        if (check(t + 1, nx, ny, b)) {
            vst[t + 1][plt[(nx - 1) * 4 + ny]][b[1]][b[2]][b[3]][b[4]] = 1;
            dfs(t + 1, nx, ny, b);
        }
    }
}
int a[5];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    while (1) {
        memset(day, 0, sizeof day);
        cin >> T;
        if (!T) {
            break;
        }
        for (int i = 1;i <= T;++i) {
            int x;
            for (int j = 1;j <= 16;++j) {
                cin >> x;
                day[i] = day[i] | (x << j);
            }
        }
        memset(vst, 0, sizeof(vst));
        memset(a, 0, sizeof(a));
        ans = 0;
        dfs(0, 2, 2, a);
        cout << ans << endl;
    }
    return 0;
}