मान लीजिए हमारे पास X और O वाला एक 2D बोर्ड है। X से घिरे सभी क्षेत्रों को कैप्चर करें। एक क्षेत्र को उस घिरे हुए क्षेत्र में सभी O को X में बदलकर कैप्चर किया जाता है।
| X | X | X | X |
| X | O | O | X |
| X | X | O | X |
| X | O | X | X |
चलाने के बाद आउटपुट होगा
| X | X | X | X |
| X | X | X | X |
| X | X | X | X |
| X | O | X | X |
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
यदि बोर्ड मौजूद नहीं है, तो खाली बोर्ड लौटाएं
i को 0 से पंक्तियों की संख्या - 1 तक की रेंज में -
यदि board[i, 0] = 'O', तो make_one(board, i, 0)
यदि board[i, पंक्ति की लंबाई - 1] = 'O', तो make_one(board, i, पंक्ति की लंबाई - 1)
i को 0 से कॉलम की संख्या - 1 तक की रेंज में -
यदि board[0, i] = 'O', तो make_one(board, 0, i)
यदि board[पंक्ति की संख्या - 1, i] = 'O', तो make_one(board, पंक्ति की संख्या - 1, i)
i को 0 से पंक्तियों की संख्या तक की रेंज में
j को 0 से कॉलम की संख्या तक की रेंज में
यदि board[i, j] = 'O', तो board[i, j] = 'X', अन्यथा 1 के लिए board[i, j] = 'O'
make_one इस तरह होगा -
यदि i < 0 या j < 0 या i >= पंक्ति संख्या या j >= कॉलम संख्या या board[i, j] = 'X' या board[i, j] = '1', तो लौट जाएं
board[i, j] := 1
make_one(board, i + 1, j), make_one(board, i - 1, j), make_one(board, i, j + 1), make_one(board, i, j - 1) कॉल करें
यह एल्गोरिदम बॉर्डर से जुड़े 'O' को पहले मार्क करता है, फिर बाकी को 'X' में बदल देता है।
बेहतर समझ के लिए निम्न कार्यान्वयन देखें -
उदाहरण
class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: None Do not return anything, modify board in-place instead.
"""
if not board:
return board
for i in range(len(board)):
if board[i][0] == 'O':
self.make_one(board, i, 0)
if board[i][len(board[0]) - 1] == 'O':
self.make_one(board, i, len(board[0]) - 1)
for i in range(len(board[0])):
if board[0][i] == 'O':
self.make_one(board, 0, i)
if board[len(board) - 1][i] == 'O':
self.make_one(board, len(board) - 1, i)
for i in range(len(board)):
for j in range(len(board[i])):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == '1':
board[i][j] = 'O'
def make_one(self, board, i, j):
if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]) or board[i][j] == 'X' or board[i][j] == '1':
return
board[i][j] = '1'
self.make_one(board, i + 1, j)
self.make_one(board, i - 1, j)
self.make_one(board, i, j + 1)
self.make_one(board, i, j - 1)
इनपुट
[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
आउटपुट
[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]