-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathready_go_part_2.py3
53 lines (50 loc) · 1.6 KB
/
ready_go_part_2.py3
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
# Copyright (c) 2023 kamyu. All rights reserved.
#
# Meta Hacker Cup 2023 Round 2 - Problem A2. Ready, Go (Part 2)
# https://www.facebook.com/codingcompetitions/hacker-cup/2023/round-2/problems/A2
#
# Time: O(R * C)
# Space: O(R * C)
#
def ready_go_part_2():
def bfs(i, j):
cnt = 0
adj = []
lookup[i][j] = True
q = [(i, j)]
while q:
new_q = []
for i, j in q:
cnt += 1
for di, dj in DIRECTIONS:
ni, nj = i+di, j+dj
if not (0 <= ni < R and 0 <= nj < C and not lookup[ni][nj]):
continue
lookup[ni][nj] = True
if A[ni][nj] == '.':
adj.append((ni, nj))
continue
new_q.append((ni, nj))
q = new_q
for i, j in adj:
lookup[i][j] = False
return adj, cnt
R, C = list(map(int, input().split()))
A = [list(input()) for _ in range(R)]
result = 0
dp = [[0]*C for _ in range(R)]
lookup = [[A[i][j] == 'B' for j in range(C)] for i in range(R)]
for i in range(R):
for j in range(C):
if not (A[i][j] == 'W' and not lookup[i][j]):
continue
adj, cnt = bfs(i, j)
if len(adj) != 1:
continue
i, j = adj[0]
dp[i][j] += cnt
result = max(result, dp[i][j])
return result
DIRECTIONS = ((1, 0), (0, 1), (-1, 0), (0, -1))
for case in range(int(input())):
print('Case #%d: %s' % (case+1, ready_go_part_2()))