0828-T3 天气预报

0828-T3 天气预报

题意

有 \(4\times 4\) 的村庄，有一朵 \(2 \times 2\) 的云，需要控制云上下左右移动，保证每个村庄都不会连续 \(7\) 天以上不下雨，也不会在不能下雨的时间下雨。问是否可以做到。

思路

搜索。

需要注意的是打标记时只用记录时间，云的位置，四个角落的村庄连续未下雨的天数。

因为四个角下雨的次数不大于中间的村庄，只要四个角不干旱，中间一定不会干旱。

代码

#include <bits/stdc++.h>
using namespace std;
int n, f[400][20];
int xz[] = {1, 0, -1, 0, 0, 2, -2, 0, 0};
int yz[] = {0, 1, 0, -1, 0, 0, 0, 2, -2};
struct node {
	pair<int,int> c[4];
	int d[5][5], t;
};
node temp, nxt;
queue <node> q;
bool vis[366][5][5][8][8][8][8];
int trans(pair<int,int> c) {
	return (c.first - 1) * 4 + c.second;
}
int main() {
	while (1) {
		cin >> n;
		if (!n) break;
		for (int i = 1; i <= n; i ++)
			for (int j = 1; j <= 16; j ++)
				cin >> f[i][j];
		temp.c[0] = {2, 2};
		temp.c[1] = {2, 3};
		temp.c[2] = {3, 2};
		temp.c[3] = {3, 3};
		for (int i = 1; i <= 4; i ++)
			for (int j = 1; j <= 4; j ++)
				temp.d[i][j] = 1;
		temp.d[2][2] = 0;
		temp.d[2][3] = 0;
		temp.d[3][2] = 0;
		temp.d[3][3] = 0;
		temp.t = 1;
		while (!q.empty()) q.pop();
		q.push(temp);
		int ans = 0;
		while (!q.empty()) {
			temp = q.front(); q.pop();
			bool ok = 1;
			for (int i = 1; i <= 4; i ++)
				for (int j = 1; j <= 4; j ++)
					if (temp.d[i][j] >= 7) ok = 0;
			for (int i = 0; i < 4; i ++) 
				if (f[temp.t][trans(temp.c[i])]) ok = 0;

			if (!ok) continue;
			if (temp.t == n) {
				ans = 1;
				break;	
			}
			for (int i = 0; i < 9; i ++) {
				nxt = temp; nxt.t ++;
				bool OK = 1;
				for (int j = 1; j <= 4; j ++)
					for (int k = 1; k <= 4; k ++) nxt.d[j][k] ++;
				for (int j = 0; j < 4; j ++) {
					int &x = nxt.c[j].first, 
						&y = nxt.c[j].second;
					x += xz[i], y += yz[i];
					if (x < 1 || y < 1 || x > 4 || y > 4) {
						OK = 0;
						break;
					}
					nxt.d[x][y] = 0;
				}
				if (!OK) continue;
				if (vis[nxt.t][nxt.c[0].first][nxt.c[0].second][nxt.d[1][1]][nxt.d[1][4]][nxt.d[4][1]][nxt.d[4][4]]) continue;
				vis[nxt.t][nxt.c[0].first][nxt.c[0].second][nxt.d[1][1]][nxt.d[1][4]][nxt.d[4][1]][nxt.d[4][4]] = 1;
				q.push(nxt);
			}
		}
		cout << ans << "\n";
		memset(vis, 0, sizeof(vis));
	}
	return 0;
}