PythonProblemSolving/SurroundedRegion.py at master · ebaumstarck/PythonProblemSolving · GitHub

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
'''
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region .

For example,
X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

'''

'''
recursive

'''
fromBoardimportBoard
fromBoardimportPoint

defis_o(board, i, j):
"""Checks whether this position has an 'O'."""
return (i<board.get_num_rows() -1andj<board.get_num_cols() -1and
board.get_by_pos(i,j) =='O')

defis_region_x_surrounded(board, i, j, region):
"""Determines whether the region is surrounded by 'X's.

 Args:
 board: The board to check.
 i: The row index to examine.
 j: The column index to examine.
 region: A list of row-column tuples that have 'O's in them.

 Returns:
 Whether the region is surrounded by 'X's or not, and adds all
 'O' positions to 'region'.
 """
# Implement.
if (i, j) inregion:
returnTrue
ifi<0orj<0ori>=board.get_num_rows() orj>=board.get_num_cols():
returnFalse
value=board.get_by_pos(i,j)
ifvalue=='X':
returnTrue
else:
region.add((i,j))
return (is_region_x_surrounded(board, i-1, j, region) and
is_region_x_surrounded(board, i+1, j, region) and
is_region_x_surrounded(board, i, j-1, region) and
is_region_x_surrounded(board, i, j+1, region))

defsolver(board):
# check the board without border
region=set()
num_rows=board.get_num_rows()
num_cols=board.get_num_cols()
foriinrange(1,num_rows-1):
forjinrange(1,num_cols-1):
ifis_o(board,i,j):
sub_region=set([(i, j)])
ifis_region_x_surrounded(board, i, j, sub_region):
# Replace all positions in 'sub_region' with 'X's.
print"Sub region: %s"%sub_region
forposinsub_region:
print" Pos: %s"%pos
board.set_by_pos(pos[0], pos[1], 'X')

# # check the neighbour
# region.update(sub_region)
# region.update(check(board,i-1,j))
# region.update(check(board,i+1,j))
# region.update(check(board,i,j-1))
# region.update(check(board,i,j+1))
returnregion

b=Board(4,4,'X')
# args: row,col,letter
b.set_by_pos(1,1,'O')
b.set_by_pos(1,2,'O')
b.set_by_pos(2,2,'O')
b.set_by_pos(3,2,'O')

printstr(b)
printsolver(b)
# print b.getitem(p)
# print b.get_by_pos(2,2)
# print b.get_num_rows()
# print b.get_num_cols()