結果

問題 No.3428 Palindromic Path (Easy)
コンテスト
ユーザー NakLon131
提出日時 2026-01-11 15:49:22
言語 Rust
(1.92.0 + proconio + num)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 996 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 25,000 ms
コンパイル使用メモリ 412,108 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-11 15:50:05
合計ジャッジ時間 25,896 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::{input, marker::Chars};
fn main() {
    input! {
		n: usize, // グリッドサイズ
		s: [Chars; n], // グリッドにある文字列
	}

	// dfs
	let mut cnt = 0;
	let mut select = Vec::new();
	dfs(n, &s, 0, 0, &mut select, &mut cnt);

	println!("{}", cnt);
}

fn dfs(n: usize, s: &Vec<Vec<char>>, 
	row: usize, col: usize,
	select: &mut Vec<char>,
	cnt: &mut usize,
) {
	// 文字選択
	select.push(s[row][col]);

	// すべて通った
	if row == n-1 && col == n-1 {
		// println!("{}", select.iter().join(" "));

		// 回文判定
		if iskaibun(&select) {
			// 回文なら個数をカウント
			*cnt += 1;
		}
		return;
	}

	// 右か下へ移動
	if row != n-1 {
		dfs(n, s, row+1, col, select, cnt);
		// 戻す
		select.pop();
	}
	if col != n-1 {
		dfs(n, s, row, col+1, select, cnt);
		// 戻す
		select.pop();
	}
}

// 回文
fn iskaibun(s: &Vec<char>) -> bool {
	let sz = s.len();
	for i in 0..sz / 2 {
		if s[i] != s[sz - 1 - i] {
			return false;
		}
	}
	true
}
0