おはようございます！
私が住んでいるところは12日まで休みですが、13日にD社のコーディングテストがあるので…。
うーん…。無理矢理パソコンの前に座りました。
D社もコーディングテストの模試を公開しているので、そのうちの一つを解いてみたいと思います。
問題
正方形の大きさの格子状の庭に、咲いた花または咲いていない花を植えました。
この庭の花が全部咲くのに何日かかるのか知りたいです。ある日に咲いた花の前後左右の4方向にある花は、次の日に花を咲かせます。
現在の庭園の状態を盛り込んだ2次元リストgardenが与えられた時、すべての花が咲くのに何日かかるのかreturnするようにsolution関数を作成してください。
説明
現在の庭園の状態を盛り込んだ2次元リストgardenがsolution関数のParameterとして与えられます。
- 庭園の一辺の長さは2以上100以下です。
- 庭園の状態を盛り込んだ2次元リスト
gardenの元素は0または1です。 - もう咲いた花は
1で、まだ咲いていない花は0で表現します。 - 庭に最低1個の花が咲いています。
Returnの説明
花が全部咲くのに何日かかるのか返します。
入出力例
| garden | return |
|---|---|
| [[0, 0, 0], [0, 1, 0], [0, 0, 0]] | 2 |
| [[1, 1], [1, 1]] | 0 |
1番の庭園
1番の庭園の現在の状態です。
一日が経つとこうなります。
二日が経つとこうなります。
結局、二日が過ぎると庭の花が全部咲きます。
2番の庭園
もう全部咲いているので、0日経つとすべての花が咲きます。
回答
私の例
# 私の例
def solution(garden):
answer = 0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
# dx、dyは東、西、南、北のような座標と関連したテストでよく使われる部分です！
arr = []
# arrは、次に周辺の畑を1にするために保存するリストです
while(len(arr)) < len(garden) ** 2:
# (len(arr))はarrの長さ、すなわち、現在値が1人座標の数であり、len(garden)**2は畑の総数です。
arr = []
for i in range(len(garden)):
for j in range(len(garden[0])):
if garden[i][j] == 1:
arr.append([i,j])
for i in arr:
for j in range(4):
x=i[0] + dx[j]
y=i[1] + dy[j]
if (x>=0 and x<len(garden)) and (y>=0 and y<len(garden)):
garden[x][y] = 1
# すべての座標を探索しながら1の座標をarrに追加します。
# arrに追加された座標の東、南、西、北に順にアクセスしながらOORでなければ（-1より大き、len(garden)より小さい場合)
# 当値を1に設定します。
answer += 1
return answer - 1
shiracamusさんのの例
# @shiracamusさんのの例
def solution(garden):
days = 0
while True:
zeros = [(y, x, any(garden[nx][ny] == 1
for ny, nx in ((y-1,x),(y+1, x),(y,x-1),(y, x+1))
if 0 <= ny < len(garden) and 0<= nx < len(garden[ny])))
for y, row in enumerate(garden)
for x, value in enumerate(row)
if value == 0]
if not zeros:
return days
days += 1
for y, x, grow in zeros:
if grow:
garden[y][x] = 1
WolfMoonさんの例
# @WolfMoonさんの例
import numpy as np
def solution(garden):
n = len(garden)
g = np.ones((n+2, n+2), dtype=int)
for i in range(n):
for j in range(n):
g[i+1][j+1] = garden[i][j]
day = 0
while True:
if g.sum() == (n+2)**2:
break
day += 1
g2 = g.copy()
for i in range(1, n+1):
for j in range(1, n+1):
if g[i, j] == 1:
g2[i-1, j] = g2[i+1, j] = g2[i, j-1] = g2[i, j+1] = 1
g = g2.copy()
return day
nkay _さんの例
# @nkay _さんの例
import numpy as np
from scipy.ndimage import binary_dilation
def solution(garden):
days = 0
g = np.asarray(garden)
while not g.all():
days += 1
g = binary_dilation(g)
return days
エンジニアさん達の例がますます追加されています…。
感想
ムズい！(この問題の制限時間は20分です。)
この問題、解ける方法が本当に多いと思います。
私が住んでいるところは、これと似たような問題が本当に多くコーディングテストとして出てくるようです。
勉強します
(日本語は未熟なので、文法が違ったり、ぎこちなければ教えてください！)