The 2022 ICPC Asia Nanjing Regional Contest（A.Stop, Yesterday Please No More）

#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;
}