ตรวจสอบว่าคำอยู่ในกริด (Grid) หรือไม่ด้วย Python

โจทย์: กำหนดกริด/แมทริกซ์ของตัวอักษร ตรวจสอบว่าคำที่กำหนดมีอยู่ในกริดหรือไม่ คำอาจปรากฏได้ 4 ทิศทาง: แนวนอนซ้าย-ขวา, แนวตั้งบน-ล่าง หากพบคืน True มิฉะนั้น False

ตัวอย่าง

input_str = "python" → Output: True

อัลกอริทึม (DFS + Backtracking)

• ฟังก์ชัน find_grid(matrix, input_str, row_pos, col_pos, row_count, col_count, degree)
• ถ้า degree == len(input_str) → คืน True
• ถ้าตำแหน่งอยู่นอกขอบเขต → คืน False
• ถ้าตัวอักษรตรงกับ input_str[degree]:
  • เก็บค่าเดิม, ทับด้วย '#' (กันซ้ำ)
  • เรียก DFS 4 ทิศทาง (บน, ล่าง, ซ้าย, ขวา) รวมผลด้วย OR
  • คืนค่าเดิม (Backtrack)
  • คืนผลลัพธ์
• มิฉะนั้น คืน False

ฟังก์ชันหลัก solve วนลูปทุกเซลล์เป็นจุดเริ่มต้น หากพบตัวแรกตรง เรียก find_grid

โค้ดตัวอย่าง

def find_grid(matrix, input_str, row_pos, col_pos, row_count, col_count, degree):
    if degree == len(input_str):
        return True
    if row_pos < 0 or col_pos < 0 or row_pos >= row_count or col_pos >= col_count:
        return False
    if matrix[row_pos][col_pos] == input_str[degree]:
        temp = matrix[row_pos][col_pos]
        matrix[row_pos] = matrix[row_pos][:col_pos] + '#' + matrix[row_pos][col_pos+1:]
        result = (find_grid(matrix, input_str, row_pos-1, col_pos, row_count, col_count, degree+1) |
                  find_grid(matrix, input_str, row_pos+1, col_pos, row_count, col_count, degree+1) |
                  find_grid(matrix, input_str, row_pos, col_pos-1, row_count, col_count, degree+1) |
                  find_grid(matrix, input_str, row_pos, col_pos+1, row_count, col_count, degree+1))
        matrix[row_pos] = matrix[row_pos][:col_pos] + temp + matrix[row_pos][col_pos+1:]
        return result
    else:
        return False

def solve(matrix, input_str, row_count, col_count):
    if len(input_str) > row_count * col_count:
        return False
    for row in range(row_count):
        for col in range(col_count):
            if matrix[row][col] == input_str[0]:
                if find_grid(matrix, input_str, row, col, row_count, col_count, 0):
                    return True
    return False

word_grid = ["pghsf", "ykdgh", "tkghi", "hnsjs", "ojfgh", "nrtyu"]
print(solve(word_grid, "python", 6, 5))

Input / Output

Input: ["pghsf", "ykdgh", "tkghi", "hnsjs", "ojfgh", "nrtyu"], "python"
Output: True