結果

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

ソースコード

diff # 

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

const int MOD = 1000000007;
int N, M;
vector<string> grid;
int dp[201][201][201];

// Returns number of palindromic paths from (i1,j1) coming from (0,0)
// and (i2,j2) coming from (N-1, M-1)
// where t = number of steps from start, and (i2, j2) can be calculated from t
int solve(int i1, int j1, int i2) {
    int t = i1 + j1;
    int j2 = N + M - 2 - t - i2;

    // Out of bounds
    if (i1 >= N || j1 >= M || i2 < 0 || j2 < 0 || i2 >= N || j2 >= M)
        return 0;
    // Current grid cells do not match
    if (grid[i1][j1] != grid[i2][j2])
        return 0;
    // If the pointers have crossed or met (at center or adjacent)
    if (abs(i1 - i2) + abs(j1 - j2) <= 1)
        return 1;

    int &res = dp[i1][j1][i2];
    if (res != -1)
        return res;
    res = 0;
    // 4 ways to move: (down/down), (right/right), (down/right), (right/down)
    res = (res + solve(i1 + 1, j1, i2 - 1)) % MOD; // down, up
    res = (res + solve(i1, j1 + 1, i2 - 1)) % MOD; // right, up
    res = (res + solve(i1 + 1, j1, i2)) % MOD;     // down, left
    res = (res + solve(i1, j1 + 1, i2)) % MOD;     // right, left
    return res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    grid.resize(N);
    for (int i = 0; i < N; ++i) cin >> grid[i];
    memset(dp, -1, sizeof dp);

    cout << solve(0, 0, N - 1) << '\n';
    return 0;
}
0