Chương trình phát hiện các chu kỳ trong lưới 2D bằng Python

Giả sử chúng ta có một mảng 2D các ký tự được gọi là lưới kích thước m x ​​n. Chúng ta phải kiểm tra xem chúng ta có thể phát hiện ra một chu trình bên trong nó hay không. Ở đây, một chu kỳ là một đường đi có độ dài từ 4 trở lên trong lưới bắt đầu và kết thúc ở cùng một vị trí. Chúng ta có thể di chuyển theo bốn hướng (lên, xuống, trái hoặc phải), nếu nó có cùng giá trị với ô hiện tại và chúng ta không thể truy cập lại một số ô.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là True, vì các ô màu xanh lá cây đang hình thành chu kỳ.

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

• TRẮNG:=0, XÁM:=1, ĐEN:=2

• R:=số hàng của lưới

• C:=số cột của lưới

• color:=một bản đồ trống, có giá trị mặc định là 0

• Định nghĩa một hàm dfs (). Điều này sẽ lấy r, c, pr:=-1, pc:=-1

• color [r, c]:=GRAY

• cho mỗi cặp (x, y) bằng di, do

  • (nr, nc):=(r + x, c + y)

  • nếu 0 <=nr

    • nếu màu [nr, nc] giống với màu TRẮNG thì

      • nếu dfs (nr, nc, r, c) là true thì

        • trả về True

      • ngược lại khi màu [nr, nc] giống với màu XÁM thì

        • trả về True

    • color [r, c]:=BLACK

    • trả về Sai

    • Từ phương thức chính, thực hiện như sau

    • đối với r trong phạm vi 0 đến R - 1, thực hiện

      • đối với c trong phạm vi 0 đến C - 1, thực hiện

        • nếu màu [r, c] giống với màu TRẮNG thì

          • nếu dfs (r, c) là true thì

            • trả về True

• trả về Sai

Ví dụ

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

from collections import defaultdict
di = [(0,1),(1,0),(0,-1),(-1,0)]
def solve(grid):
   WHITE,GRAY,BLACK = 0 ,1 ,2
   R,C = len(grid),len(grid[0])

   color = defaultdict(int)

   def dfs(r,c,pr=-1,pc=-1):
      color[r,c] = GRAY
      for x,y in di:
         nr,nc = r+x,c+y
         if (0<=nr<R and 0<=nc<C and grid[r][c] == grid[nr][nc] and (nr,nc)!=(pr,pc)):
            if color[nr,nc]==WHITE:
               if dfs(nr,nc,r,c):
                  return True
            elif color[nr,nc] == GRAY:
               return True

      color[r,c] = BLACK
      return False

   for r in range(R):
      for c in range(C):
         if color[r,c] == WHITE:
            if dfs(r,c):
               return True
   return False
matrix = [["m","m","m","p"],["m","k","m","m"],["m","m","s","m"],["f","m","m","m"]]
print(solve(matrix))

Đầu vào

7, [5,1,4,3]

Đầu ra

True