結果
問題 | No.2855 Move on Grid |
ユーザー |
|
提出日時 | 2024-08-25 15:26:56 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 767 ms / 3,000 ms |
コード長 | 2,202 bytes |
コンパイル時間 | 12,673 ms |
コンパイル使用メモリ | 404,940 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-25 15:27:27 |
合計ジャッジ時間 | 29,219 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
fn main() {input!{n: usize, m: usize, k: usize,a: [[usize; m]; n],}// 探索経路全て置き換え可能if n+m-1 <= k {println!("{}", INF);return;}// x未満なら置き換えと、二分探索で決めるlet mut ok = 0;let mut ng = INF + 1;let d = vec!{(!0, 0), (0, !0), (1, 0), (0, 1)}; // 上左下右for _ in 0..50 {let md = (ng + ok) / 2;if enabled_move(n, m, &d, md, k, &a) {ok = md;}else {ng = md;}}println!("{}", ok);}// n: usize, m: usize, k: usize,// a: [[usize; m]; n],fn enabled_move(n: usize, m: usize, // 縦横d: &Vec<(usize, usize)>, // 4方向移動border: usize, // 置き換え条件k: usize, // 置き換え回数a: &Vec<Vec<usize>>) // グリッド-> bool{// (1,1)->(N,M)へ移動する際に置き換え回数のminlet mut cost = vec![vec![INF; m]; n];cost[0][0] = if a[0][0] < border {1} else {0};// コストの小さい順に見る(ダイクストラ)let mut hp = BinaryHeap::new();hp.push(Reverse((cost[0][0], (0, 0))));while hp.len() > 0 {let (now_cost, (now_x, now_y)) = hp.pop().unwrap().0;if now_cost > cost[now_x][now_y] { continue; }// 4方向移動for k in 0..4 {// 範囲外の移動チェックlet next_x = now_x.wrapping_add(d[k].0);let next_y = now_y.wrapping_add(d[k].1);if next_x >= n || next_y >= m {continue; }// 移動後のコストlet next_cost = if a[next_x][next_y] < border {now_cost+1} else {now_cost};if next_cost < cost[next_x][next_y] {cost[next_x][next_y] = next_cost;hp.push(Reverse((next_cost, (next_x, next_y))));}}}if cost[n-1][m-1] <= k {true} else {false}}// const MOD17: usize = 1000000007;// const MOD93: usize = 998244353;const INF: usize = 1_000_000_000;// let dx = vec![!0, 0, 1, 0]; // 上左下右// let dy = vec![0, !0, 0, 1]; // 上左下右#[allow(unused)]use proconio::{input, marker::Chars, marker::Usize1};#[allow(unused)]use std::{mem::swap,cmp::min, cmp::max,cmp::Reverse,collections::HashSet, collections::BTreeSet,collections::HashMap, collections::BTreeMap,collections::BinaryHeap,collections::VecDeque,iter::FromIterator,};