結果
問題 | No.2731 Two Colors |
ユーザー |
|
提出日時 | 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 |
ソースコード
#![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!(),}}}}