D - Dungeon Master

2 secs 1024 MB

uni_kakurenbo

問題

提出

テストケース

解説

概要

基本的なアルゴリズムの実装を問う問題です．

問題原案：uni_kakurenbo

略解

$\max\,\{\,0,\,($ 通路マスの連結成分の個数 $) - 1 \,\}$ が答えになることが示せます．
通路マスの連結成分の個数は BFS, DFS, Union-Find などを用いて求められます．

解説

$Ⅰ.$ 移動できるマスの言い換え

大雑把にいうと，「ある道のマスにいる人は，上下左右に隣接しているか，ワープホールによって結ばれている，他の道のマスへ移動することができる」となります．

$Ⅱ.$ グリッドの特徴

与えられるグリッドは，いくつかの，隣接したマスへの移動によって互いに行き来ができる $1$ つ以上の道のマスの集合に分割することができます．
以降これを部屋と呼びます．

つまり，設置したワープホールによって各部屋間を移動できるようにすればよいです．

※ . と # が逆でした．申し訳ございません
Grid_0

$Ⅲ.$ 設置すべきワープホール

同じ部屋に属するマス同士は既に互いに行き来することが可能なので，設置すべきワープホールは異なる部屋に属するマス同士を結ぶものに限ってよいです．
また，異なる部屋に属するマス同士であればどのマス同士を繋いでもよいです．

したがって，部屋の位置やマスの個数は重要でなく，「グリッド上に部屋がいくつ存在するか」のみが分かれば，最低限必要なワープホールの個数を求めることができます．これは，BFS, DFS, Union-Find などのアルゴリズムを用いることで，簡単に求まります．
(詳しい解説は他サイト様へ委ねます．基礎的かつとても有用なアルゴリズム・データ構造なので，知らなかった方はぜひ調べてみてください．)

「実装例」の項では BFS, Union-Find による解答の一例を紹介します．
再帰関数を用いて DFS を実装する場合はスタックオーバーフローなどのエラーに注意してください．

$O(N^2)$ や $O(\alpha(N^2)N^2)$ 時間で解けます．

$Ⅳ.$ 最低限必要なワープホールの個数

以上の議論から，この問題は「 $N$ 個の部屋同士をワープホールで $2$ つずつ互いに繋いでいくとき，すべての部屋同士を(間接的に)繋げるためには最低で何組のワープホールが必要か？」という問題に帰着させることができます．
これは実際にいくつかの簡単な図を書いてみるとすぐにわかります．

結論は $N-1$ 個となりますが，これは数学的帰納法的に考えることで比較的簡単に確かめられます．

部屋の数が $1$ 個のとき， $0$ 組のワープホールで達成されます．
部屋の数が $2$ 個のとき， $1$ 組のワープホールによってそれらをつなげば，部屋の数が $1$ 個になったと見なせます．
部屋の数が $3$ 個のとき， $1$ 組のワープホールによってある $2$ つの部屋同士をつなげば，部屋の数が $2$ 個になったと見なせます．
部屋の数が $4$ 個のとき， $1$ 組のワープホールによってある $2$ つの部屋同士をつなげば，部屋の数が $3$ 個になったと見なせます．
$\vdots$
部屋の数が $k$ 個のとき， $1$ 組のワープホールによってある $2$ つの部屋同士をつなげば，部屋の数が $k-1$ 個になったと見なせます．

$1$ 組のワープホールで，孤立した部屋の個数が $1$ ずつ減っていくと考えると， $N$ 個の部屋すべてを繋げる( $1$ つにまとめる)のに必要なワープホールは最小で $N-1$ 組であるとわかります．

$Ⅴ.$ コーナーケース

グリッド上に道のマスが一つも存在しないときに注意してください．
部屋の個数が $0$ となりますが，答えは $-1$ ではありません．

このとき既に問題文中の条件は満たされているため，答えは $0$ となります．

$Ⅵ.$ グラフへの導入

この問題は，道のマスを頂点としたグラフ上で木を構築するために必要な残りの辺の本数を求めていることに違いありません．
(部屋は連結成分に当たります．)
「グラフ」や「木」といった用語が聞きなれない方はぜひ調べてみてください．

$Ⅶ.$ 発展

$1)$ 類題

ACL Biginner Contest $\hspace{0.15em}$ C - Connect Cities
ABC 269 $\hspace{0.15em}$ D - Do use hexagon grid
POJ $\hspace{0.15em}$ No.2386 - Lake Counting
AHC 013 $\hspace{0.15em}$ A - Server Room

実装例

C++

xxxxxxxxxx
 
// Union-Find
// 壁のマスをすべて接続してしまうと実装が楽です．(超頂点を一つ持ちます)
// 隣接を確認する向きは，右と下などの異なる方向の2つの向きだけで十分です．
​
#include <bits/stdc++.h>
#include <atcoder/dsu>
​
using namespace std;
using namespace atcoder;
​
signed main() {
    int h, w; cin >> h >> w;
    vector<string> G(h); for(auto &g : G) cin >> g;
​
    auto id = [&w](int i, int j) { return i*w + j; };
​
    dsu uf(w*h + 1);
​
    for(int i=0; i<h; i++) for(int j=0; j<w; j++) {
        if(G[i][j] == '#') { uf.merge(id(i,j), h*w); continue; }  // 壁のマスを1つにまとめる
        if(i+1 < h and G[i+1][j] == '.') uf.merge(id(i,j), id(i+1,j));
        if(j+1 < w and G[i][j+1] == '.') uf.merge(id(i,j), id(i,j+1));
    }
​
    cout << max(0, (int)uf.groups().size() - 2) << endl;  // 壁のマスの分も一緒に取り除く
​
    return 0;
}
​

Python

xxxxxxxxxx
 
# Union-Find
# 壁のマスをすべて接続してしまうと実装が楽です．(超頂点を一つ持ちます)
# 隣接を確認する向きは，右と下などの異なる方向の2つの向きだけで十分です．
​
from itertools import product
​
# Thanks to: https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
​
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
​
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
​
        if x == y:
            return
​
        if self.parents[x] > self.parents[y]:
            x, y = y, x
​
        self.parents[x] += self.parents[y]
        self.parents[y] = x
​
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
​
    def group_count(self):
        return len(self.roots())
​
h, w = map(int, input().split())
G = [input() for _ in [0] * h]
​
uf = UnionFind(h*w+1)
​
def id(i, j):
    return i*w + j
​
for i, j in product(range(0, h), range(0, w)):
    if G[i][j] == '#': uf.union(id(i,j), h*w); continue  # 壁のマスを一つにまとめる
    if i+1 < h and G[i+1][j] == '.': uf.union(id(i,j), id(i+1,j))
    if j+1 < w and G[i][j+1] == '.': uf.union(id(i,j), id(i,j+1))
​
print(max(0, uf.group_count() - 2))  # 壁のマスの分も一緒に取り除く
​

Python

xxxxxxxxxx
 
# BFS
from collections import deque
from itertools import product
from sys import stdin
​
input = stdin.readline
DXY = ((0, 1), (1, 0), (0, -1), (-1, 0))
​
h, w = map(int, input().split())
​
G = [input() for _ in [0] * h]
​
que = deque()
visited = [False] * (h * w)
cnt = 0
​
def id(i, j):
    return i*w + j
​
for si, sj in product(range(0, h), range(0, w)):
    if G[si][sj] == '#': continue
​
    cnt += not visited[id(si,sj)]
    que.append((si, sj))
​
    while len(que) > 0:
        i, j = que.popleft()
        for di, dj in DXY:
            ni, nj = i + di, j + dj
            if not 0 <= ni < h or not 0 <= nj < w: continue
            if visited[id(ni,nj)] or G[ni][nj] == '#': continue
            visited[id(ni,nj)] = True
            que.append((ni, nj))
​
print(max(0, cnt - 1))

$\\$

余談

またやってしまいました．
ACL Beginner Contest で既出でした．(「類題」のところにあります)
仕方ないので許してください☆
問題文作るのがかなり難しかったです．

D - Dungeon Master

概要

略解

解説

Ⅰ.Ⅰ.Ⅰ. 移動できるマスの言い換え

Ⅱ.Ⅱ.Ⅱ. グリッドの特徴

Ⅲ.Ⅲ.Ⅲ. 設置すべきワープホール

Ⅳ.Ⅳ.Ⅳ. 最低限必要なワープホールの個数

Ⅴ.Ⅴ.Ⅴ. コーナーケース

Ⅵ.Ⅵ.Ⅵ. グラフへの導入

Ⅶ.Ⅶ.Ⅶ. 発展

1)1)1) 類題

実装例

C++

Python

Python

余談

$Ⅰ.$ 移動できるマスの言い換え

$Ⅱ.$ グリッドの特徴

$Ⅲ.$ 設置すべきワープホール

$Ⅳ.$ 最低限必要なワープホールの個数

$Ⅴ.$ コーナーケース

$Ⅵ.$ グラフへの導入

$Ⅶ.$ 発展

$1)$ 類題