結果

問題 No.3429 Palindromic Path (Hard)
コンテスト
ユーザー chiaoi
提出日時 2026-01-11 14:33:34
言語 Rust
(1.92.0 + proconio + num)
結果
AC  
実行時間 843 ms / 2,000 ms
コード長 1,247 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 25,941 ms
コンパイル使用メモリ 412,252 KB
実行使用メモリ 128,096 KB
最終ジャッジ日時 2026-01-11 14:34:02
合計ジャッジ時間 25,851 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::input;
#[allow(unused)]
use proconio::marker::*;
#[allow(unused)]
use std::collections::*;

const MOD: usize = 998_244_353;

fn main() {
    input! {
        n: usize,
        c: [Bytes; n],
    };

    let mut memo = HashMap::new();
    println!("{}", f((0, 0), (n - 1, n - 1), n, &c, &mut memo));
}

fn f(
    (i0, j0): (usize, usize),
    (i1, j1): (usize, usize),
    n: usize,
    c: &Vec<Vec<u8>>,
    memo: &mut HashMap<(usize, usize, usize, usize), usize>,
) -> usize {
    if i0 + j0 == n - 1 {
        return 1;
    }
    if c[i0][j0] != c[i1][j1] {
        return 0;
    }

    if memo.contains_key(&(i0, j0, i1, j1)) {
        return *memo.get(&(i0, j0, i1, j1)).unwrap();
    }

    let mut res = 0;
    for (di0, dj0) in [(1, 0), (0, 1)] {
        for (di1, dj1) in [(!0, 0), (0, !0)] {
            let ni0 = i0.wrapping_add(di0);
            let nj0 = j0.wrapping_add(dj0);
            let ni1 = i1.wrapping_add(di1);
            let nj1 = j1.wrapping_add(dj1);
            if ni0 < n && nj0 < n && ni1 < n && nj1 < n && ni0 <= ni1 && nj0 <= nj1 {
                res += f((ni0, nj0), (ni1, nj1), n, c, memo);
                res %= MOD;
            }
        }
    }
    memo.insert((i0, j0, i1, j1), res);
    res
}
0