結果

問題 No.124 門松列(3)
ユーザー titiatitia
提出日時 2022-10-26 01:07:17
言語 Rust
(1.77.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 2,003 bytes
コンパイル時間 1,256 ms
コンパイル使用メモリ 158,632 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-16 21:25:54
合計ジャッジ時間 2,113 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 3 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 3 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 1 ms
4,376 KB
testcase_17 AC 1 ms
4,380 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 1 ms
4,376 KB
testcase_20 AC 1 ms
4,380 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 1 ms
4,380 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 AC 1 ms
4,380 KB
testcase_28 AC 3 ms
4,376 KB
testcase_29 AC 3 ms
4,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unnecessary parentheses around `if` condition
  --> Main.rs:71:8
   |
71 |     if (ans==1<<60){
   |        ^          ^
   |
   = note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
   |
71 -     if (ans==1<<60){
71 +     if ans==1<<60 {
   |

warning: variable `W` should have a snake case name
 --> Main.rs:4:10
  |
4 |     let (W, H): (i32, i32) = {
  |          ^ help: convert the identifier to snake case (notice the capitalization): `w`
  |
  = note: `#[warn(non_snake_case)]` on by default

warning: variable `H` should have a snake case name
 --> Main.rs:4:13
  |
4 |     let (W, H): (i32, i32) = {
  |             ^ help: convert the identifier to snake case: `h`

warning: 3 warnings emitted

ソースコード

diff # 

use std::collections::VecDeque;

fn main() {
    let (W, H): (i32, i32) = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    };

    let mut map=vec![Vec::new();H as usize];

    for i in 0..H{

        let a: Vec<i64> = {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|x| x.parse().unwrap())
                .collect()
        };

        map[i as usize]=a;
    }

    let mut dp=vec![vec![vec![(1 as i64) <<60;12];W as usize];H as usize];
    let mut q:VecDeque<(i32,i32,i32)>=VecDeque::new();
    let dx: [i32; 4] = [-1, 0, 1, 0];
    let dy: [i32; 4] = [0, -1, 0, 1];

    for i in 0..11{
        dp[0][0][i]=0;
        q.push_back((0,0,(i as i32)));
    }

    while q.len()>0{
        let (x0,y0,a)=q.pop_front().unwrap();

        for i in 0..4{
            let x:i32 = x0 as i32 +dx[i];
            let y:i32 = y0 as i32 +dy[i];

            if 0<=x && x<H && 0<=y && y<W{
                let b=map[x0 as usize][y0 as usize] as i32;
                let c=map[x as usize][y as usize] as i32;

                if a!=b && a!=c && b!=c && ((a<b && b>c) || (a>b && b<c)){
                    if dp[x as usize][y as usize][b as usize]>dp[x0 as usize][y0 as usize][a as usize]+1{
                        dp[x as usize][y as usize][b as usize]=dp[x0 as usize][y0 as usize][a as usize]+1;
                        q.push_back((x,y,b))
                    }
                }

            }
        }
    }

    let mut ans=1<<60;

    for i in 1..10{
        let k =dp[H as usize-1][W as usize-1][i];

        if ans>k{
            ans=k;
        }
    }

    if (ans==1<<60){
        println!("{}",-1);
    }
    else{
        println!("{}",ans);
    }


}
0