Submission #19499469

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;//三年竞赛一场空，不开long long见祖宗
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define x first
#define y second
typedef pair<int, int> pii;
const ll mod = 998244353;
const int maxn = 5010;
const int inf = 0x3f3f3f3f;
char g[maxn][maxn];
ll dp[maxn][maxn];
ll numd[maxn][maxn], numr[maxn][maxn];
int n, m, k;
ll p[maxn];

void init()
{
    p[0] = 1;
    for(int i = 1; i < maxn; i++)
        p[i] = p[i - 1] * 3 % mod;
}

int main()
{   
    init();
    cin >> n >> m >> k;
    for(int i = 1; i <= k; i++)
    {
        int x, y;
        string s;
        cin >> x >> y >> s;
        g[x][y] = s[0];
    }
    
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 1; j--)
            numr[i][j] = numr[i][j + 1] + (g[i][j] == 0);
    for(int j = 1; j <= m; j++)
        for(int i = n; i >= 1; i--)
            numd[i][j] = numd[i + 1][j] + (g[i][j] == 0);
    dp[1][1] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            ll num = dp[i][j];
            if(g[i][j] == 'R' || g[i][j] == 'X') dp[i][j + 1] += num * p[numd[i + 1][j]] % mod, dp[i][j + 1] %= mod;
            if(g[i][j] == 'D' || g[i][j] == 'X') dp[i + 1][j] += num * p[numr[i][j + 1]] % mod, dp[i + 1][j] %= mod;
            if(g[i][j] == 0)
            {
                dp[i + 1][j] += 2 * num * p[numr[i][j + 1]] % mod;
                dp[i + 1][j] %= mod;
                dp[i][j + 1] += 2 * num * p[numd[i + 1][j]] % mod;
                dp[i][j + 1] %= mod;
            }
        }
    if(g[n][m] == 0) dp[n][m] *= 3, dp[n][m] %= mod;
    cout << dp[n][m] << endl;
}

Submission Info

Judge Result