-
Notifications
You must be signed in to change notification settings - Fork 0
/
capture_surrounded.py
59 lines (52 loc) · 1.64 KB
/
capture_surrounded.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
59
# for https://leetcode.com/problems/surrounded-regions/
from pprint import pprint
def check_neighbours(board, i, j):
if i>-1 and j>-1 and i<len(board) and j<len(board[0]) and board[i][j] == 'O':
# print(board,'hi')
board[i][j] = 1
# print(board,'bye')
check_neighbours(board, i-1, j)
check_neighbours(board, i, j-1)
check_neighbours(board, i+1, j)
check_neighbours(board, i, j+1)
def capture_surrounded_Os(board):
"""
board: 2d list
modifies board in-place
"""
if board == []:
return
leni = len(board)
lenj = len(board[0])
print('start')
pprint(board)
# recursively fill 'O's with 1's, starting at edges
for i in range(leni):
if board[i][0] == 'O':
check_neighbours(board, i, 0)
if board[i][lenj-1] == 'O':
check_neighbours(board, i, lenj-1)
for j in range(lenj):
if board[0][j] == 'O':
check_neighbours(board, 0, j)
if board[leni-1][j] == 'O':
check_neighbours(board, leni-1, j)
print('should have more 1\'s:')
pprint(board)
# fill the rest with 'X's
for i in range(leni):
for j in range(lenj):
if board[i][j] == 1:
board[i][j] = 'O'
else:
board[i][j] = 'X'
print('\n----INPUT #1----\n')
board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
capture_surrounded_Os(board)
print('final')
pprint(board)
print('\n----INPUT #2----\n')
board = [["X","X","X","X"],["X","O","O","X"],["X","O","O","X"],["X","O","X","X"]]
capture_surrounded_Os(board)
print('final')
pprint(board)