-
Notifications
You must be signed in to change notification settings - Fork 1.6k
/
Copy pathminesweeper.py
79 lines (76 loc) · 2.42 KB
/
minesweeper.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
# Time: O(m * n)
# Space: O(m + n)
# dfs
class Solution(object):
def updateBoard(self, board, click):
"""
:type board: List[List[str]]
:type click: List[int]
:rtype: List[List[str]]
"""
if board[click[0]][click[1]] == 'M':
board[click[0]][click[1]] = 'X'
return board
stk = [click]
while stk:
r, c = stk.pop()
cnt = 0
adj = []
for dr in xrange(-1, 2):
for dc in xrange(-1, 2):
if dr == dc == 0:
continue
nr, nc = r+dr, c+dc
if not (0 <= nr < len(board) and 0 <= nc < len(board[r])):
continue
if board[nr][nc] == 'M':
cnt += 1
elif board[nr][nc] == 'E':
adj.append((nr, nc))
if cnt:
board[r][c] = chr(cnt + ord('0'))
continue
board[r][c] = 'B'
for nr, nc in adj:
board[nr][nc] = ' '
stk.append((nr, nc))
return board
# Time: O(m * n)
# Space: O(m + n)
# dfs
class Solution2(object):
def updateBoard(self, board, click):
"""
:type board: List[List[str]]
:type click: List[int]
:rtype: List[List[str]]
"""
if board[click[0]][click[1]] == 'M':
board[click[0]][click[1]] = 'X'
return board
q = [click]
while q:
new_q = []
for r, c in q:
cnt = 0
adj = []
for dr in xrange(-1, 2):
for dc in xrange(-1, 2):
if dr == dc == 0:
continue
nr, nc = r+dr, c+dc
if not (0 <= nr < len(board) and 0 <= nc < len(board[r])):
continue
if board[nr][nc] == 'M':
cnt += 1
elif board[nr][nc] == 'E':
adj.append((nr, nc))
if cnt:
board[r][c] = chr(cnt + ord('0'))
continue
board[r][c] = 'B'
for nr, nc in adj:
board[nr][nc] = ' '
new_q.append((nr, nc))
q = new_q
return board