競プロ初中級者100問

AOJ1160 島はいくつある？

この記事で使うアルゴリズム

深さ優先探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=ja

この問題は深さ優先探索を用いて解くことができます。

解説

深さ優先探索は再帰で実装することができます。Pythonのデフォルト値だと小さすぎるので、再帰処理の上限を引き上げます。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import sys
sys.setrecursionlimit(10**7)

dxdy = ((0,1),(0,-1),(1,0),(-1,0),(-1,1),(1,-1),(1,1),(-1,-1))
ans = []
while(1):
    W, H = map(int, input().split())
    if (W==0 and H==0):
        break
    mp = []
    for h in range(H):
        line = input()
        line = line.split()
        line = [-int(l) for l in line]
        mp.append(line)
    def dfs(h,w):
        mp[h][w] = k
        for dx, dy in dxdy:
            nw = w + dx
            nh = h + dy
            if (0 <= nh < H and 0 <= nw < W):
                if (mp[nh][nw] == -1):
                    dfs(nh, nw)
    k = 0
    for h in range(H):
        for w in range(W):
            if mp[h][w] == -1:
                k += 1
                dfs(h,w)
    ans.append(k)
for a in ans:
    print(a)

記事情報

  • 投稿日：2020年6月1日
  • 最終更新日：2020年6月1日