GMOJ S6814 【染色大战】

Description

有一张有 $n \times m$ 个像素点的图片，位置为 $(i, j)$ 的像素点的颜色是 $c_{i, j}$，颜色相同的点在同一个连通块中。现在有 $q$ 次操作，每次会将与点 $(1, 1)$ 在同一个连通块内的像素点的颜色改为 $x_i$，现在请你求出每次操作完后点 $(1, 1)$ 所在的联通块的像素点的数量。

$$1 \leq n, m \leq 10^3, 1 \leq q \leq 2 \times 10^5$$

Solution

一道有趣的题目。

考虑维护与点 $(1, 1)$ 所在连通块相邻的点，按照颜色分类，丢进 vector 里存储即可。

修改颜色的时候，只需要把 vector 里颜色为当前修改颜色的点标记为在连通块内并且从这个点向外扩展，并且在这个过程中统计答案就可以了。

注意开始的时候要把点 $(1, 1)$ 最开始所在的连通块求出来，不然会 WA 掉。

由于一个点只会被查询一次，因此时间复杂度为 $O(nm)$。

如果用 map 的话时间复杂度是 $O(nm \log nm)$ 的，也能过，我不会用 vector，写的是 map。

Code

• vector 做法（来自 lxl，已经过授权）

#include<cstdio>
#include<cctype>
#include<vector>
using namespace std;
constexpr int mov[][2] = { {-1},{0,-1},{0,1}, {1} };
inline int Read()noexcept
{
	char c;
	for (c = getchar(); !isdigit(c); c = getchar());
	int ans = c - '0';
	for (c = getchar(); isdigit(c); ans = (ans * 10) + (c - '0'), c = getchar());
	return ans;
}
int color[1001][1001], state[1001][1001];
struct Point
{
	int x, y;
	Point()noexcept :x(), y() {}
	Point(const int& _x, const int& _y)noexcept :x(_x), y(_y) {}
	inline bool operator<(const Point& other)const noexcept
	{
		if (x != other.x)
		{
			return x < other.x;
		}
		return y < other.y;
	}
};
int main()noexcept
{
	const int n = Read(), m = Read(), q = Read(), K = Read(), size = n * m;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			color[i][j] = Read();
			state[i][j] = 2;
		}
	}
	vector<Point>* edge = new vector<Point>[static_cast<size_t>(K) + 1];
	Point* que = new Point[static_cast<size_t>(size) + 1];
	const auto update = [&edge, &que, &n, &m](const Point& start, const int& col)noexcept {
		int head = 0, tail = 0;
		if (state[start.x][start.y] != 0)
		{
			que[tail++] = start;
			state[start.x][start.y] = 0;
			const auto in_range = [&n, &m](const Point& p)noexcept {
				return (1 <= p.x && p.x <= n) && (1 <= p.y && p.y <= m);
			};
			while (head < tail)
			{
				const auto& pos = que[head++];
				for (int i = 0; i < 4; ++i)
				{
					const Point to(pos.x + mov[i][0], pos.y + mov[i][1]);
					if (in_range(to))
					{
						if (color[to.x][to.y] == col)
						{
							if (state[to.x][to.y] != 0)
							{
								que[tail++] = to;
								state[to.x][to.y] = 0;
							}
						}
						else if (state[to.x][to.y] == 2)
						{
							edge[color[to.x][to.y]].push_back(to);
							state[to.x][to.y] = 1;
						}
					}
				}
			}
		}
		return tail;
	};
	int ans = update(Point(1, 1), color[1][1]);
	for (int i = 1; i <= q; ++i)
	{
		const int col = Read();
		for (const auto& p : edge[col])
		{
			ans += update(p, col);
		}
		edge[col].clear();
		printf("%d\n", ans);
	}
	delete[] edge;
	delete[] que;
	return 0;
}

• map 做法

#include <map>
#include <cstdio>
#define maxN 1010
std::map<int, std::map<int, int> > f[2];
int Ans = 0, n = 0, m = 0, q = 0;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int color[maxN][maxN], flag[maxN][maxN];
int queue[maxN * maxN][2], size[maxN * maxN];
int read ()
{
	int x = 0;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}
	return x;
}
void bfs (int Sx, int Sy, int C)
{
	int head = 1, tail = 2;
	queue[1][0] = Sx, queue[1][1] = Sy;
	while(head < tail)
	{
		int x = queue[head][0], y = queue[head][1];
		for(register int k = 0;k <= 3; k++)
		{
			int nx = x + dx[k];
			int ny = y + dy[k];
			if(nx >= 1 && nx <= n && ny >= 1 && ny <= m)
			{
				if(color[nx][ny] == C)
				{
					Ans++;
					flag[nx][ny] = color[nx][ny] = 0;
					queue[tail][0] = nx, queue[tail][1] = ny; 
					tail++;
				}
				else if(flag[nx][ny] == 1)
				{
					flag[nx][ny] = 2;
					int Now = ++size[color[nx][ny]];
					f[0][color[nx][ny]][Now] = nx;
					f[1][color[nx][ny]][Now] = ny;
				}
			}
		}
		head++;
	}
}
int main ()
{
	scanf("%d %d %d %*d", &n, &m, &q);
	for(register int i = 1;i <= n; i++)
	{
		for(register int j = 1;j <= m; j++)
		{
			flag[i][j] = 1;
			color[i][j] = read();
		}
	}
	Ans = 1;
	int Now = color[1][1];
	flag[1][1] = color[1][1] = 0;
	bfs(1, 1, Now);
	while(q--)
	{
		int Color = read();
		for(register int i = 1;i <= size[Color]; i++)
		{
			int x = f[0][Color][i], y = f[1][Color][i];
			if(flag[x][y] == 2)
			{
				Ans++;
				Now = color[x][y];
				flag[x][y] = color[x][y] = 0;
				bfs(x, y, Now);
			}
		}
		size[Color] = 0;
		f[0][Color].clear(), f[1][Color].clear();
		printf("%d\n", Ans);
	}
	return 0;
}