【二维差分】ICPC南京 A

https://codeforces.com/gym/104128/problem/A

题意

 

思路

二维差分+经典模型

考虑如果没有洞那么经历操作之后会剩下什么样子的袋鼠。发现上下左右移动可以看成是边界在移动，边界一直保持一个原初的矩形形状，而且上下移动和左右移动没有任何关系。一旦边界移动到了一个位置，这个位置前面的袋鼠都会消失。

所以记录u,d,l,r,表示在移动时所产生的最小矩阵的上下左右边界，这样剩下的袋鼠数量就是有(d-u+1)*(r-l+1)个。

加入有洞的情况，发现洞产生的路径都可以通过平移获得，那么就只维护一条路径，就是从(0,0)点开始的路径，那么所有的点（i，j）的路径就是（0，0）点开始的路径上的点加（i，j）。 那么我们要维护有洞会让袋鼠消失多少，只有在u<=x<=d,l<=y<=r的才是有效被消失的袋鼠，那么就维护mp[i][j]表示从（i，j)点开始会让多少只袋鼠消失，发现对于点(x,y),只会对一个矩形内的数加1，左上角为(u-x,l-y),右下角为（d-x,r-y)的矩形，变成二维差分维护，那么在二维差分中给一个点加1等于给它往右往下的全部点加1.

注意：要去除经过的重复的点，重复点不能重复计算答案，因为他们去除的是同一片袋鼠。

Code：

#include 
 
constexpr int N = 1e3 + 10;
constexpr int mod = 998244353;
constexpr int Inf = 0x3f3f3f3f;
 
std::string s;
 
int n, m, k;
int f[N][N];
int vis[N][N];
 
void add(int x1, int y1, int x2, int y2) {
	f[x1][y1] ++;
	f[x2 + 1][y1] --;
	f[x1][y2 + 1] --;
	f[x2 + 1][y2 + 1] ++;
}
void solve() {
	std::cin >> n >> m >> k;
	for (int i = 0; i <= n + 5; i ++) {
		for (int j = 0; j <= m + 5; j ++) {
			vis[i][j] = f[i][j] = 0;
		}
	}
	std::cin >> s;
	int sz = s.size();
	s = " " + s;
	int u = 1, d = n, l = 1, r = m;
	int U = 1, D = n, L = 1, R = m;
	for (int i = 1; i <= sz; i ++) {
		if (s[i] == 'U') {
			u ++;
			d ++;
		}else if (s[i] == 'D') {
			u --;
			d --;
		}else if (s[i] == 'L') {
			l ++;
			r ++;
		}else {
			l --;
			r --;
		}
		U = std::max(U, u);
		D = std::min(D, d);
		L = std::max(L, l);
		R = std::min(R, r);
	}
	if (L > R || U > D) {
		if (k) {
			std::cout << 0 << "\n";
		}else {
			std::cout << n * m << "\n";
		}
		return;
	}
	int del = (R - L + 1) * (D - U + 1) - k;
	if (del < 0) {
		std::cout << 0 << "\n";
		return;
	}
	add(U, L, D, R);
	vis[L][U] = 1;
	for (int i = 1; i <= sz; i ++) {
		if (s[i] == 'L') {
			L --;
			R --;
		}else if (s[i] == 'R') {
			L ++;
			R ++;
		}else if (s[i] == 'U') {
			U --;
			D --;
		}else {
			U ++;
			D ++;
		}
		if (vis[L][U]) continue;
		vis[L][U] = 1;
		add(U, L, D, R);
	}
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			if (f[i][j] == del) ans ++;
		}
	}
	std::cout << ans << "\n";
}
signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
 
	int t = 1;
	std::cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}