-
Notifications
You must be signed in to change notification settings - Fork 0
/
dfs.py
58 lines (43 loc) · 1.69 KB
/
dfs.py
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# -*- coding: utf-8 -*-
N = 10
M = 12
def generate_garden():
# 課題の庭を生成
garden = [["W", ".", ".", ".", ".", ".", ".", ".", ".", "W", "W", "."],
[".", "W", "W", "W", ".", ".", ".", ".", ".", "W", "W", "W"],
[".", ".", ".", ".", "W", "W", ".", ".", ".", "W", "W", "."],
[".", ".", ".", ".", ".", ".", ".", ".", ".", "W", "W", "."],
[".", ".", ".", ".", ".", ".", ".", ".", ".", "W", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", ".", "W", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", ".", "W", "W", "."],
[".", ".", "W", ".", ".", ".", ".", ".", ".", "W", ".", "."],
[".", "W", ".", "W", ".", ".", ".", ".", ".", "W", ".", "."],
["W", ".", "W", ".", "W", ".", ".", ".", ".", ".", "W", "."],
[".", "W", ".", "W", ".", ".", ".", ".", ".", ".", "W", "."],
[".", ".", "W", ".", ".", ".", ".", ".", ".", ".", "W", "."]]
return garden
garden = generate_garden()
def dfs(x, y):
garden[x][y] = "."
# 8方向に対してループを繰り返す
for dx in (-1, 0, 1):
for dy in (-1, 0, 1):
nx = x + dx
ny = y + dy
if (0 <= nx and nx < N
and 0 <= ny and ny < M
and garden[nx][ny] == "W"):
dfs(nx, ny)
# 対象となるポイントが見つからなくなったら終了
return
def solve():
res = 0
for i in range(0, N - 1):
for j in range(0, M - 1):
if(garden[i][j] == "W"):
dfs(i, j)
res += 1
print res
def __main__():
solve()
__main__()