Submission #67334295

---

Source Code Expand

use std::{collections::HashMap, io};

#[derive(Default)]
struct Scanner {
    buffer: Vec<String>,
}
impl Scanner {
    fn next<T: std::str::FromStr>(&mut self) -> T {
        loop {
            if let Some(token) = self.buffer.pop() {
                return token.parse().ok().expect("Failed parse");
            }
            let mut input = String::new();
            io::stdin().read_line(&mut input).expect("Failed read");
            self.buffer = input.split_whitespace().rev().map(String::from).collect();
        }
    }
}

const DIR_R: [i32; 8] = [1, 0, -1, 0, 1, 1, -1, -1];
const DIR_C: [i32; 8] = [0, 1, 0, -1, 1, -1, 1, -1];

fn dfs(u: usize, adj: &Vec<Vec<usize>>, vis: &mut Vec<bool>) {
    vis[u] = true;
    for &v in &adj[u] {
        if !vis[v] {
            vis[v] = true;
            dfs(v, adj, vis);
        }
    }
}

fn main() {
    let mut scanner = Scanner::default();
    let (h, w, k): (i32, i32, usize) = (scanner.next(), scanner.next(), scanner.next());
    let mut rc = Vec::new();
    let mut mp = HashMap::new();
    for i in 0..k {
        let (r, c): (i32, i32) = (scanner.next(), scanner.next());
        rc.push((r, c));
        mp.insert((r, c), i);
    }

    let mut adj = vec![Vec::new(); k + 2];
    for (id, (r, c)) in rc.into_iter().enumerate() {
        for l in 0..8 {
            let nr = r + DIR_R[l];
            let nc = c + DIR_C[l];
            if nr <= 0 || nc > w {
                adj[id].push(k);
                adj[k].push(id);
            } else if nc <= 0 || nr > h {
                adj[id].push(k + 1);
                adj[k + 1].push(id);
            } else if let Some(&nid) = mp.get(&(nr, nc)) {
                adj[id].push(nid);
            }
        }
    }

    let mut vis = vec![false; k + 2];
    dfs(k, &adj, &mut vis);
    if vis[k + 1] {
        println!("No");
    } else {
        println!("Yes");
    }
}

Submission Info

Judge Result