Submission #73329228

---

Source Code Expand

use proconio::{input, marker::Chars};
use std::collections::VecDeque;

fn dfs_bipartite(
    u: usize,
    adj: &Vec<Vec<usize>>,
    match_right: &mut Vec<Option<usize>>,
    visited: &mut Vec<bool>,
) -> bool {
    for &v in &adj[u] {
        if visited[v] {
            continue;
        }
        visited[v] = true;
        if match_right[v].is_none() || dfs_bipartite(match_right[v].unwrap(), adj, match_right, visited) {
            match_right[v] = Some(u);
            return true;
        }
    }
    false
}

fn main() {
    input! {
        N: usize,
        A: i32,
        B: i32,
        S: [Chars; N],
    }

    let mut cells = vec![];
    let mut cell_to_id = vec![vec![None; N]; N];
    for i in 0..N {
        for j in 0..N {
            if S[i][j] == '.' {
                cell_to_id[i][j] = Some(cells.len());
                cells.push((i as i32, j as i32));
            }
        }
    }
    let V = cells.len();

    let moves = [
        (A, B),
        (B, A),
        (B, -A),
        (A, -B),
        (-A, -B),
        (-B, -A),
        (-B, A),
        (-A, B),
    ];

    let mut graph = vec![vec![]; V];
    for (idx, &(i, j)) in cells.iter().enumerate() {
        for &(dx, dy) in &moves {
            let ni = i + dx;
            let nj = j + dy;
            if ni >= 0 && ni < N as i32 && nj >= 0 && nj < N as i32 {
                if let Some(nidx) = cell_to_id[ni as usize][nj as usize] {
                    graph[idx].push(nidx);
                }
            }
        }
    }

    let mut color = vec![-1; V];
    for start in 0..V {
        if color[start] == -1 {
            let mut q = VecDeque::new();
            color[start] = 0;
            q.push_back(start);
            while let Some(u) = q.pop_front() {
                for &v in &graph[u] {
                    if color[v] == -1 {
                        color[v] = 1 - color[u];
                        q.push_back(v);
                    } else if color[v] == color[u] {
                        panic!("not bipartite");
                    }
                }
            }
        }
    }

    let mut left_ids = vec![];
    let mut right_ids = vec![];
    let mut id_to_left = vec![None; V];
    let mut id_to_right = vec![None; V];

    for (id, &c) in color.iter().enumerate() {
        if c == 0 {
            id_to_left[id] = Some(left_ids.len());
            left_ids.push(id);
        } else {
            id_to_right[id] = Some(right_ids.len());
            right_ids.push(id);
        }
    }

    let n_left = left_ids.len();
    let n_right = right_ids.len();

    let mut adj_left = vec![vec![]; n_left];
    for (orig_u, &c) in color.iter().enumerate() {
        if c == 0 {
            let u = id_to_left[orig_u].unwrap();
            for &orig_v in &graph[orig_u] {
                if color[orig_v] == 1 {
                    let v = id_to_right[orig_v].unwrap();
                    adj_left[u].push(v);
                }
            }
        }
    }

    let mut match_right = vec![None; n_right];
    for u in 0..n_left {
        let mut visited = vec![false; n_right];
        dfs_bipartite(u, &adj_left, &mut match_right, &mut visited);
    }

    // 交替路BFS：未マッチの左頂点から開始
    let mut vis_l = vec![false; n_left];
    let mut vis_r = vec![false; n_right];
    let mut q = VecDeque::new();

    for u in 0..n_left {
        if !match_right.contains(&Some(u)) {
            vis_l[u] = true;
            q.push_back(('L', u));
        }
    }

    while let Some((side, idx)) = q.pop_front() {
        if side == 'L' {
            // 左 → 右：非マッチ辺を使う
            for &v in &adj_left[idx] {
                if match_right[v] != Some(idx) && !vis_r[v] {
                    vis_r[v] = true;
                    q.push_back(('R', v));
                }
            }
        } else {
            // 右 → 左：マッチ辺を使う
            if let Some(u2) = match_right[idx] {
                if !vis_l[u2] {
                    vis_l[u2] = true;
                    q.push_back(('L', u2));
                }
            }
        }
    }

    let mut in_independent_set = vec![false; V];
    for (orig_id, &c) in color.iter().enumerate() {
        if c == 0 {
            let pos = id_to_left[orig_id].unwrap();
            if vis_l[pos] {
                in_independent_set[orig_id] = true;
            }
        } else {
            let pos = id_to_right[orig_id].unwrap();
            if !vis_r[pos] {
                in_independent_set[orig_id] = true;
            }
        }
    }

    let mut result = vec![vec!['.'; N]; N];
    for i in 0..N {
        for j in 0..N {
            if S[i][j] == '#' {
                result[i][j] = '#';
            }
        }
    }
    for (idx, &(i, j)) in cells.iter().enumerate() {
        if in_independent_set[idx] {
            result[i as usize][j as usize] = 'o';
        }
    }

    for row in result {
        println!("{}", row.iter().collect::<String>());
    }
}

Submission Info

Compile Error

warning: variable `N` should have a snake case name
  --> src/main.rs:25:9
   |
25 |         N: usize,
   |         ^ help: convert the identifier to snake case: `n`
   |
   = note: `#[warn(non_snake_case)]` on by default

warning: variable `A` should have a snake case name
  --> src/main.rs:26:9
   |
26 |         A: i32,
   |         ^ help: convert the identifier to snake case: `a`

warning: variable `B` should have a snake case name
  --> src/main.rs:27:9
   |
27 |         B: i32,
   |         ^ help: convert the identifier to snake case: `b`

warning: variable `S` should have a snake case name
  --> src/main.rs:28:9
   |
28 |         S: [Chars; N],
   |         ^ help: convert the identifier to snake case (notice the capitalization): `s`

warning: variable `V` should have a snake case name
  --> src/main.rs:41:9
   |
41 |     let V = cells.len();
   |         ^ help: convert the identifier to snake case (notice the capitalization): `v`

Judge Result