模拟边界(不是袋鼠)移动,通过二维差分维护左上角和右下角,同时注意排除重复的点
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; #define endl "\n" typedef long long ll; const int N = 1e3 + 5; int f[N][N]; int main(){ ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int T = 1; cin >> T; while(T--){ int n, m, k; cin >> n >> m >> k; for(int i = 0; i <= n + 1; i++){ for(int j = 0; j <= m + 1; j++){ f[i][j] = 0; } } string s; cin >> s; map<pair<int, int>, int> vis; //模拟边界移动,而不是袋鼠 int L = 1, R = m, U = 1, D = n; int l = L, r = R, u = U, d = D; for(int i = 0; i < (int)s.size(); i++){ //所以这里是反的 if(s[i] == 'U') u++, d++; else if(s[i] == 'D') u--, d--; else if(s[i] == 'L') l++, r++; else l--, r--; L = max(l, L); R = min(r, R); U = max(u, U); D = min(d, D); } if(D < U || R < L){ if(k == 0) cout << n * m << endl; else cout << 0 << endl; continue; } auto get = [&](int x1, int y1, int x2, int y2){ if(vis[{x1, y1}]) return; vis[{x1, y1}] = 1; f[x1][y1]++; f[x2 + 1][y2 + 1]++; f[x1][y2 + 1]--; f[x2 + 1][y1]--; }; get(U, L, D, R); l = L, r = R, u = U, d = D; for(int i = 0; i < (int)s.size(); i++){ if(s[i] == 'U') u--, d--; else if(s[i] == 'D') u++, d++; else if(s[i] == 'L') l--, r--; else l++, r++; get(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][j] - f[i - 1][j - 1]; } } int ans = 0, cnt = (D - U + 1) * (R - L + 1); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(cnt - f[i][j] == k) ans++; } } cout << ans << endl; } return 0; }View Code
标签:cout,Contest,int,cin,Regional,Please,++,else,-- From: https://www.cnblogs.com/zhujio/p/17659334.html