-
Notifications
You must be signed in to change notification settings - Fork 0
/
surrounded_regions.py
110 lines (87 loc) · 2.59 KB
/
surrounded_regions.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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
from bisect import bisect_left as bl, bisect_right as br, bisect
from collections import defaultdict as dd, deque, Counter
from heapq import merge, heapify, heappop, heappush, nsmallest
from itertools import combinations
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from sys import stdin, stdout
MOD = pow(10, 9) + 7
MOD2 = 998244353
PI = 3.141592653589793
# input str
def inp():
return stdin.readline().strip()
# input int
def iinp():
return int(inp())
# map and array of int
def mp():
return map(int, inp().split())
def liinp():
return list(mp())
# array of string/char
def lmps():
return map(str, inp().split())
# output (solutions)
def out(var, end="\n"):
stdout.write(str(var)+end)
def outa(*var, end="\n"):
stdout.write(' '.join(map(str, var))+end)
# dp
def l1d(n, val=0):
return [val for i in range(n)] # dp[i]
def l2d(n, m, val=0):
return [l1d(m, val) for j in range(n)] # dp[i][j]
# functions
def DFS(board, pos):
height = len(board)
width = len(board[0])
visited = []
while pos:
ii, jj = pos.pop()
board[ii][jj] = '+'
for row, col in [(ii-1, jj), (ii+1, jj), (ii, jj-1), (ii, jj+1)]:
if 0<=row<height and 0<=col<width and (row, col) not in visited\
and board[row][col]=='O':
board[row][col] = '+'
pos.append((row, col))
visited.append((row, col))
for row in range(height):
for col in range(width):
if board[row][col]=='+':
board[row][col] = 'O'
elif board[row][col]=='O':
board[row][col] = 'X'
return board
def solve(board):
pos = list()
height = len(board)
width = len(board[0])
if width<3 or height<3:
return board
for ii in range(height):
for jj in range(width):
if ii==0 or ii==height-1:
if board[ii][jj]=='O':
if (ii, jj) not in pos:
pos.append((ii, jj))
if jj==0 or jj==width-1:
if board[ii][jj]=='O':
if (ii, jj) not in pos:
pos.append((ii, jj))
if pos:
return DFS(board, pos)
else:
for row in range(height):
for col in range(width):
if board[row][col]=='O':
board[row][col] = 'X'
return board
# ----- main() -----
if __name__ == '__main__':
board = [
["O","X"],
["O","X"],
["O","X"],
["X","O"],
]
print(solve(board))