蟻本をPythonで（LakeCounting）

本記事はnoteで書いていた記事の転載です。（noteからはてなブログに移行したため）　　　

AtCoderのコンテストに参加したり，蟻本を読んだりし始めました。

使用言語はPythonの予定。そこで，コンテストの参加記録や蟻本で勉強したことを書いていければいいなと思っています。

今回は第二章の全探索（深さ優先探索）。POJ2386のLakeCountingです。

C++とPythonで違うところはほとんどないので，そのまま真似して書けばＯＫ．

N,M = map(int,input().split())

field = [""]*M
for i in range(N):
   field[i] = list(input())

def dfs(x, y):
   field[x][y] = "."

   for dx in range(-1,2):
       for dy in range(-1,2):
           nx = x+dx
           ny = y+dy
           if  0 <= nx and nx < N  and 0 <= ny and ny < M and field[nx][ny] == "W":
               dfs(nx,ny)

res = 0
for i in range(N):
   for j in range(M):
       if field[i][j] == "W":
           dfs(i,j)
           res += 1
print(res)

個人的に蟻本のコードで気になっていた部分は，DFSの処理の中の，ifの条件式でした。

別に水たまりかどうかの判定に庭の端かどうかは関係なくね？と思っていました。ので，if文の部分を以下のように変更してみました。

これを

if  0 <= nx and nx < N  and 0 <= ny and ny < M and field[nx][ny] == "W":

これに

if  field[nx][ny] == "W":

すると，こうなりました。

    if  field[nx][ny] == "W":
IndexError: string index out of range

ということで，水たまりかどうかの判定ではなく，field[ ][ ]というlistにアクセスする際に，indexの外側の値でアクセスしないようにするために必要だったということでした。4方向にfor文を回しているので確かにその判定が必要ですね。

でも，ということはifの中身の条件式の順番を入れ替えて

if  field[nx][ny] == "W" and 0 <= nx and nx < N  and 0 <= ny and ny < M:

としても

  if  field[nx][ny] == "W" and 0 <= nx and nx < N  and 0 <= ny and ny < M:
IndexError: string index out of range

同じエラーがでますね。ifでは条件式がFalseになった時点で後続の条件文を判定しないので，このようになるのかなと思います。