結果

問題 No.1916 Making Palindrome on Gird
ユーザー LyricalMaestro
提出日時 2025-03-16 04:24:07
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 921 ms / 3,000 ms
コード長 2,679 bytes
コンパイル時間 13,212 ms
コンパイル使用メモリ 398,920 KB
実行使用メモリ 128,596 KB
最終ジャッジ日時 2025-03-16 04:24:33
合計ジャッジ時間 21,163 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::{HashMap, VecDeque};
use std::io::{self, BufRead};

const MOD: usize = 1_000_000_007;
const DIRECTION0: [(isize, isize); 2] = [(1, 0), (0, 1)];
const DIRECTION1: [(isize, isize); 2] = [(-1, 0), (0, -1)];

fn main() {
    let stdin = io::stdin();
    let mut input = stdin.lock().lines();
    
    let first_line = input.next().unwrap().unwrap();
    let mut hw = first_line.split_whitespace().map(|x| x.parse::<usize>().unwrap());
    let h = hw.next().unwrap();
    let w = hw.next().unwrap();
    
    let mut s: Vec<Vec<char>> = Vec::new();
    for line in input.take(h) {
        s.push(line.unwrap().chars().collect());
    }
    
    if s[0][0] != s[h - 1][w - 1] {
        println!("0");
        return;
    }
    
    let mut dp: HashMap<(usize, usize, usize, usize), usize> = HashMap::new();
    let mut queue: VecDeque<(usize, usize, usize, usize)> = VecDeque::new();
    
    dp.insert((0, 0, h - 1, w - 1), 1);
    queue.push_back((0, 0, h - 1, w - 1));
    
    let mut answer = 0;
    
    while let Some((h0, w0, h1, w1)) = queue.pop_front() {
        let x = *dp.get(&(h0, w0, h1, w1)).unwrap();
        if (h0 as isize - h1 as isize).abs() + (w0 as isize - w1 as isize).abs() <= 1 {
            answer = (answer + x) % MOD;
            continue;
        }
        
        for &(dh0, dw0) in &DIRECTION0 {
            let new_h0 = h0 as isize + dh0;
            let new_w0 = w0 as isize + dw0;
            if !(0 <= new_h0 && new_h0 < h as isize && 0 <= new_w0 && new_w0 < w as isize) {
                continue;
            }
            
            for &(dh1, dw1) in &DIRECTION1 {
                let new_h1 = h1 as isize + dh1;
                let new_w1 = w1 as isize + dw1;
                if !(0 <= new_h1 && new_h1 < h as isize && 0 <= new_w1 && new_w1 < w as isize) {
                    continue;
                }
                
                let new_h0 = new_h0 as usize;
                let new_w0 = new_w0 as usize;
                let new_h1 = new_h1 as usize;
                let new_w1 = new_w1 as usize;
                
                if !(new_h0 <= new_h1 && new_w0 <= new_w1) {
                    continue;
                }
                
                if s[new_h0][new_w0] == s[new_h1][new_w1] {
                    let key = (new_h0, new_w0, new_h1, new_w1);
                    let entry = dp.entry(key).or_insert(0);
                    *entry = (*entry + x) % MOD;
                    
                    if *entry == x { // 初回追加時にキューへ
                        queue.push_back(key);
                    }
                }
            }
        }
    }
    println!("{}", answer);
}
0