結果

問題 No.2731 Two Colors
ユーザー Yukino DX.
提出日時 2024-04-20 09:54:50
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 134 ms / 3,000 ms
コード長 4,217 bytes
コンパイル時間 12,139 ms
コンパイル使用メモリ 398,052 KB
実行使用メモリ 26,380 KB
最終ジャッジ日時 2024-10-12 05:19:58
合計ジャッジ時間 15,770 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#![allow(unused_imports)]
//use itertools::{iproduct, Itertools};
use proconio::input;
use proconio::marker::*;
use std::cmp::Reverse;
use std::collections::*;
fn main() {
input! {
h:usize,
w:usize,
a:[[usize;w];h],
}
let mut pq = [BinaryHeap::new(), BinaryHeap::new()];
let mut seen = [vec![vec![false; w]; h], vec![vec![false; w]; h]];
seen[1][0][0] = true;
seen[0][h - 1][w - 1] = true;
for Pos { x, y } in Pos::new(0, 0).neigh4(h, w) {
pq[1].push(Reverse((a[x][y], x, y)));
seen[1][x][y] = true;
}
for Pos { x, y } in Pos::new(h - 1, w - 1).neigh4(h, w) {
pq[0].push(Reverse((a[x][y], x, y)));
seen[0][x][y] = true;
}
let mut ans = 0;
let mut mod2 = 1;
let mut colors = vec![vec![2; w]; h];
colors[0][0] = 1;
colors[h - 1][w - 1] = 0;
while let Some(Reverse((_, x, y))) = pq[mod2].pop() {
if colors[x][y] != 2 {
continue;
}
ans += 1;
colors[x][y] = mod2;
if Pos::new(x, y)
.neigh4(h, w)
.any(|Pos { x: nx, y: ny }| colors[nx][ny] == 1 - mod2)
{
break;
}
for Pos { x: nx, y: ny } in Pos::new(x, y).neigh4(h, w) {
if seen[mod2][nx][ny] {
continue;
}
pq[mod2].push(Reverse((a[nx][ny], nx, ny)));
seen[mod2][nx][ny] = true;
}
mod2 = 1 - mod2;
}
println!("{}", ans);
}
use grid_mgr::*;
mod grid_mgr {
//[R,D,L,U]
pub const DIR4: [(usize, usize); 4] = [(0, 1), (1, 0), (0, !0), (!0, 0)];
pub const DIR8: [(usize, usize); 8] = [
(1, 0),
(1, !0),
(0, !0),
(!0, !0),
(!0, 0),
(!0, 1),
(0, 1),
(1, 1),
];
pub struct Pos {
pub x: usize,
pub y: usize,
}
impl Pos {
#[allow(dead_code)]
pub fn new(x: usize, y: usize) -> Self {
Self { x, y }
}
#[allow(dead_code)]
pub fn neigh4<'a>(&'a self, h: usize, w: usize) -> impl Iterator<Item = Pos> + 'a {
DIR4.iter().filter_map(move |&(dx, dy)| {
let nx = self.x.wrapping_add(dx);
let ny = self.y.wrapping_add(dy);
if nx < h && ny < w {
Some(Pos::new(nx, ny))
} else {
None
}
})
}
#[allow(dead_code)]
pub fn neigh8<'a>(&'a self, h: usize, w: usize) -> impl Iterator<Item = Pos> + 'a {
DIR8.iter().filter_map(move |&(dx, dy)| {
let nx = self.x.wrapping_add(dx);
let ny = self.y.wrapping_add(dy);
if nx < h && ny < w {
Some(Pos::new(nx, ny))
} else {
None
}
})
}
#[allow(dead_code)]
pub fn line<'a>(
&'a self,
h: usize,
w: usize,
dir: (usize, usize),
) -> impl Iterator<Item = Pos> + 'a {
(0..).map_while(move |i| {
let nx = self.x.wrapping_add(dir.0.wrapping_mul(i));
let ny = self.y.wrapping_add(dir.1.wrapping_mul(i));
if nx < h && ny < w {
Some(Pos::new(nx, ny))
} else {
None
}
})
}
#[allow(dead_code)]
pub fn _moveto(&self, h: usize, w: usize, dir: (usize, usize)) -> Option<Pos> {
let nx = self.x.wrapping_add(dir.0);
let ny = self.y.wrapping_add(dir.1);
if nx < h && ny < w {
Some(Pos::new(nx, ny))
} else {
None
}
}
#[allow(dead_code)]
pub fn moveto(&self, h: usize, w: usize, dir: char) -> Option<Pos> {
match dir {
'R' => self._moveto(h, w, DIR4[0]),
'D' => self._moveto(h, w, DIR4[1]),
'L' => self._moveto(h, w, DIR4[2]),
'U' => self._moveto(h, w, DIR4[3]),
_ => unreachable!(),
}
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0