Chương trình tìm trạng thái của các phòng giam sau k ngày trong python

Giả sử chúng ta có một danh sách nhị phân (1 và 0 trong danh sách) và một giá trị k khác. Mỗi giá trị trong nums đại diện cho trạng thái của một ô tù trong đó 1 biểu thị ô bị chiếm và 0 biểu thị ô trống. Vào mỗi ngày khi một ô có hai ô liền kề bị chiếm hoặc cả hai đều trống, thì ô đó sẽ bị chiếm. Nếu không, nó sẽ trở nên trống rỗng. Vì vậy, chúng ta phải tìm trạng thái của các phòng giam sau k số ngày.

Vì vậy, nếu đầu vào là nums =[1, 0, 1, 0, 0, 0, 0, 0] k =1, thì đầu ra sẽ là [0, 1, 1, 0, 1, 1, 1, 0], như chúng ta có thể nhận thấy chỉ mục đầu tiên và chỉ mục cuối cùng không bao giờ có thể bị chiếm dụng bởi vì chúng không bao giờ có thể có 2 hàng xóm.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• Xác định một hàm next_day_state (). Điều này sẽ lấy các ô
• new_cells:=một bản sao của các ô
• new_cells [0]:=0, new_cells [7]:=0
• đối với j trong phạm vi từ 1 đến 6, thực hiện
  • nếu các ô [j - 1] giống với các ô [j + 1], thì
    • new_cells [j]:=1
  • nếu không,
    • new_cells [j]:=0
• trả lại new_cells
• Từ phương thức chính, hãy làm như sau:
• đã thấy:=một bản đồ mới
• flag:=False, i:=0
• while i
• ns:=next_day_state (ô)
• nếu ns không được nhìn thấy, thì
  • đánh dấu ns là đã thấy
• nếu không,
  • cờ:=True
  • ra khỏi vòng lặp
• ô:=ns
• i:=i + 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ

import copy
class Solution:
   def next_day_state(self, cells):
      new_cells = copy.copy(cells)
      new_cells[0] = 0
      new_cells[7] = 0
      for j in range(1, 7):
         if cells[j - 1] == cells[j + 1]:
            new_cells[j] = 1
         else:
            new_cells[j] = 0
      return new_cells

   def solve(self, cells, N):
      seen = dict()
      flag, i = False, 0

      while i < N:
         ns = self.next_day_state(cells)
         if tuple(ns) not in seen:
            seen[tuple(ns)] = True
         else:
            flag = True
            break
         cells = ns
         i += 1

      if flag:
         N = N % len(seen)
         i = 0
         while i < N:
            ns = self.next_day_state(cells)
            i += 1
            cells = ns
      return cells

ob = Solution()
nums = [1, 0, 1, 0, 0, 0, 0, 0]
k = 1
print(ob.solve(nums, k))

Đầu vào

[4, 7, 2, 5], 6

Đầu ra

[0, 1, 1, 0, 1, 1, 1, 0]