| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 715660 | ateacode | Tracks in the Snow (BOI13_tracks) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
def getNeighbours(w, h, coord):
x, y = coord
valid_coords = []
if x > 0:
valid_coords.append((x-1, y))
if x < w - 1:
valid_coords.append((x + 1, y))
if y > 0:
valid_coords.append((x, y - 1))
if y < h - 1:
valid_coords.append((x, y + 1))
return valid_coords
def findMinPossibleAnimals(grid, w, h):
'''
have a 'allowed' character, and a visited coord set. You run bfs such that you can visit a character if they are a allowed character or in the visited coord set. otherwise, they must be a new character which must be saved for the next pass.
'''
allowed_char = grid[0][0]
visited_chars = set()
toVisit = [(0, 0)]
i = 0
while allowed_char != None:
i += 1
next_char = None
visited = set()
while len(toVisit) > 0:
node = toVisit.pop()
for neighbour in getNeighbours(w, h, node):
symbol = grid[neighbour[0]][neighbour[1]]
if symbol == '.' or neighbour in visited:
continue
if neighbour in visited_chars or symbol == allowed_char:
visited.add(neighbour)
toVisit.append(neighbour)
else:
next_char = grid[neighbour[0]][neighbour[1]]
visited_chars.union(visited)
allowed_char = next_char
return i
def parseGrid(h, w):
grid = []
for row in range(h):
row_inp = [c for c in input()]
grid.append(row_inp)
return grid
def main():
h, w = [int(s) for s in input().split()]
grid = parseGrid(h, w)
print(findMinPossibleAnimals(grid, w, h))
main()