পাইথনে Surrounded Regions (ঘেরা ಪ್ರದೇಶ ক্যাপচার করা)

মান করুন একটি ২D বোর্ড আছে যাতে X এবং O আছে। X দ্বারা ঘেরা সব অঞ্চল ক্যাপচার করুন। একটি অঞ্চল ক্যাপচার করা হয় সেটির সব O কে X এ পরিবর্তন করে।

প্রোগ্রাম রান করার পর আউটপুট হবে:

সমাধানের ধাপগুলো (DFS/Flood Fill):

• যদি বোর্ড না থাকে, তবে খালি বোর্ড রিটার্ন করুন

• i ০ থেকে সারি সংখ্যা - ১ পর্যন্ত

  • যদি board[i][0] == 'O', তবে make_one(board, i, 0)

  • যদি board[i][কলাম_সংখ্যা-1] == 'O', তবে make_one(board, i, কলাম_সংখ্যা-1)

• i ০ থেকে কলাম সংখ্যা - ১ পর্যন্ত

  • যদি board[0][i] == 'O', তবে make_one(board, 0, i)

  • যদি board[সারি_সংখ্যা-1][i] == 'O', তবে make_one(board, সারি_সংখ্যা-1, i)

• i ০ থেকে সারি সংখ্যা

  • j ০ থেকে কলাম সংখ্যা

    • যদি board[i][j] == 'O', তবে board[i][j] = 'X', অন্যথায় ১ হলে 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) কল করুন

নিচে ইমপ্লিমেন্টেশন দেওয়া হলো:

উদাহরণ

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"]]