博客

>Link

luogu P7411

>Description

一个



1000

∗

1000

1000*1000






1


0


0


0




∗








1


0


0


0





的矩阵，每次在一个空格子上放一头牛，每时每刻询问最少还要放多少头牛，使得每一头牛上下左右相邻的牛的头数不等于3

>解题思路

直接模拟+广搜就可以了（感觉很多人写的是深搜）

但是赛时我打的queue爆掉了才40分😡😡要用vector！

>代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define N 5000
using namespace std;

const int xxx[4] = {-1, 0, 0, 1}, yyy[4] = {0, -1, 1, 0};
struct node
{
	int x, y;
};
vector<node> q;
int n, ans, tot[N][N];
bool a[N][N], vis[N][N];

int main()
{
	int x, y, xx, yy, vx, vy, nd;
	scanf ("%d", &n);
	while (n--)
	{
		scanf ("%d%d", &x, &y);
		x += 1000, y += 1000;
		if (!a[x][y]) a[x][y] = 1;
		else
		{
			ans--;
			printf ("%d\n", ans);
			continue;
		}
		q.push_back ((node){x, y});
		vis[x][y] = 1;
		while (!q.empty())
		{
			node u = q.back();
			q.pop_back(), vis[u.x][u.y] = 0;
			if (!a[u.x][u.y]) ans++, a[u.x][u.y] = 1;
			tot[u.x][u.y] = 0;
			for (int i = 0; i < 4; i++)
			{
				xx = u.x + xxx[i], yy = u.y + yyy[i];
				tot[xx][yy]++;
				if (tot[xx][yy] == 3 && a[xx][yy])
				  for (int j = 0; j < 4; j++)
				  {
				  	vx = xx + xxx[j], vy = yy + yyy[j];
				  	if (!a[vx][vy] && !vis[vx][vy])
					  vis[vx][vy] = 1, q.push_back ((node){vx, vy});
				  }
				if (a[xx][yy]) tot[u.x][u.y]++;
				else nd = i;
			}
			if (tot[u.x][u.y] == 3)
			  vis[u.x + xxx[nd]][u.y + yyy[nd]] = 1,
			  q.push_back ((node){u.x + xxx[nd], u.y + yyy[nd]});
		}
		printf ("%d\n", ans);
	}
	return 0;
}