結果

問題 No.1916 Making Palindrome on Gird
ユーザー Mohamed Thaer
提出日時 2025-05-16 12:07:13
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,833 bytes
コンパイル時間 2,663 ms
コンパイル使用メモリ 200,752 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-16 12:07:19
合計ジャッジ時間 3,819 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 11 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N, M;
    cin >> N >> M;
    vector<string> grid(N);
    for(int i = 0; i < N; ++i) cin >> grid[i];

    // DP[k][i1][i2] = number of ways for:
    //  - pointer 1 at (i1, k-i1)
    //  - pointer 2 at (i2, N+M-2 - k - i2)
    // after k steps from the start and k steps from the end
    // We only need current and previous layer since k increases
    
    int maxstep = (N + M - 2) / 2;
    // dp[i1][i2] = for current k
    vector<vector<int>> dp(N, vector<int>(N, 0)), ndp(N, vector<int>(N, 0));
    // Base cases (k=0): both at (0,0) and (N-1,M-1)
    for (int i1 = 0; i1 < N; ++i1)
        for (int i2 = 0; i2 < N; ++i2)
            dp[i1][i2] = 0;

    // Only if the endpoints match
    if(grid[0][0] == grid[N-1][M-1])
        dp[0][N-1] = 1;

    for (int k = 1; k <= maxstep; ++k) {
        for (int i1 = 0; i1 < N; ++i1) {
            int j1 = k - i1;
            if (j1 < 0 || j1 >= M) continue;
            for (int i2 = 0; i2 < N; ++i2) {
                int j2 = (M - 1 - (k - (N - 1 - i2)));
                if (j2 < 0 || j2 >= M) continue;
                ndp[i1][i2] = 0;
                // Pointers at (i1,j1) and (i2,j2)
                if (grid[i1][j1] != grid[i2][j2]) continue;
                // Try all combinations for previous step
                for (int d1 = 0; d1 < 2; ++d1) { // 0 - from up, 1 - from left
                    int pi1 = i1 - d1, pj1 = j1 - (1 - d1);
                    if (pi1 < 0 || pj1 < 0) continue;
                    for (int d2 = 0; d2 < 2; ++d2) { // 0 - from down, 1 - from right
                        int pi2 = i2 + d2, pj2 = j2 + (1 - d2);
                        if (pi2 >= N || pj2 >= M) continue;
                        ndp[i1][i2] += dp[pi1][pi2];
                        if (ndp[i1][i2] >= MOD) ndp[i1][i2] -= MOD;
                    }
                }
            }
        }
        swap(dp, ndp);
    }

    int ans = 0;

    // For odd length, pointers meet at exactly one cell (center)
    // For even length, pointers meet at two cells
    if ((N+M)%2 == 1) {
        for (int i1 = 0; i1 < N; ++i1) {
            int j1 = maxstep - i1;
            if (j1 < 0 || j1 >= M) continue;
            int i2 = i1;
            int j2 = j1;
            ans = (ans + dp[i1][i2]) % MOD;
        }
    }
    else {
        for (int i1 = 0; i1 < N; ++i1) {
            int j1 = maxstep - i1;
            if (j1 < 0 || j1 >= M) continue;
            for (int d = 0; d < 2; ++d) {
                int i2 = i1 + d;
                int j2 = j1 + (1 - d);
                if (i2 >= N || j2 >= M) continue;
                ans = (ans + dp[i1][i2]) % MOD;
            }
        }
    }

    cout << ans << '\n';
    return 0;
}
0