Submission #74277348

---

Source Code Expand

use proconio::input;
use std::collections::VecDeque;

fn main() {
    input! {
        h: usize,
        w: usize,
        s: [String; h],
    }

    let mut visited = vec![vec![false; w]; h];
    let mut ans = 0;

    // 移動方向 (右，左，下，上)
    let dx = [0isize, 0, 1, -1];
    let dy = [1isize, -1, 0, 0];

    // 全マス探索
    for i in 0..h {
        for j in 0..w {
            if s[i].as_bytes()[j] == b'.' && !visited[i][j] {
                let mut touches_boundary = false;
                let mut queue = VecDeque::new();
                
                // BFS 開始
                queue.push_back((i, j));
                visited[i][j] = true;

                while let Some((r, c)) = queue.pop_front() {
                    if r == 0 || r == h - 1 || c == 0 || c == w - 1 {
                        touches_boundary = true;
                    }

                    // 隣接マス探索
                    for k in 0..4 {
                        let nr = r as isize + dx[k];
                        let nc = c as isize + dy[k];

                        // 範囲内か確認
                        if nr >= 0 && nr < h as isize && nc >= 0 && nc < w as isize {
                            let nr = nr as usize;
                            let nc = nc as usize;
                            // 白マスかつ未訪問ならキューに追加
                            if s[nr].as_bytes()[nc] == b'.' && !visited[nr][nc] {
                                visited[nr][nc] = true;
                                queue.push_back((nr, nc));
                            }
                        }
                    }
                }

                if !touches_boundary {
                    ans += 1;
                }
            }
        }
    }

    println!("{}", ans);
}

Submission Info

Judge Result