Chương trình tìm trạng thái bàn cờ 2048 sau một lần vuốt trong Python

Mô tả bài toán

Cho bàn cờ game 2048 (ma trận 4x4, ô trống dùng 0) và chuỗi hướng vuốt direction ("U", "D", "L", "R"). Tìm trạng thái bàn cờ tiếp theo. Khi vuốt, tất cả số di chuyển xa nhất có thể theo hướng đó, các số giống nhau liền kề được cộng gộp đúng một lần.

Ví dụ: vuốt trái ("L") biến ma trận đầu vào thành ma trận kết quả như hình minh họa.

Thuật toán

1. Xoay bàn cờ để luôn xử lý vuốt trái ("L"):
   • "R": xoay ngược chiều kim đồng hồ 2 lần (180°).
   • "U": xoay ngược chiều kim đồng hồ 1 lần (90°).
   • "D": xoay ngược chiều kim đồng hồ 3 lần (270°).
2. Với mỗi hàng (4 hàng):
   • Lấy danh sách các phần tử khác 0.
   • Duyệt từ trái sang phải: nếu 2 phần tử liền kề bằng nhau → gộp (nhân 2), xóa phần tử thứ 2.
   • Điền 0 vào cuối cho đủ 4 phần tử.
   • Gán lại hàng.
3. Xoay ngược lại để khôi phục hướng gốc:
   • "R": xoay 2 lần.
   • "U": xoay 3 lần (tương đương xuôi chiều 1 lần).
   • "D": xoay 1 lần.
4. Trả về bàn cờ mới.

Triển khai Python

class Solution:
    def solve(self, board, direction):
        # Xoay bàn cờ để chuẩn hóa về vuốt trái
        if direction == "R":
            board = rot_anti_clock_dir(rot_anti_clock_dir(board))
        elif direction == "U":
            board = rot_anti_clock_dir(board)
        elif direction == "D":
            board = rot_anti_clock_dir(rot_anti_clock_dir(rot_anti_clock_dir(board)))
        
        # Xử lý từng hàng: nén và gộp
        for i in range(4):
            row = [x for x in board[i] if x]  # Loại bỏ 0
            for j in range(3):
                if j + 1 < len(row) and row[j] == row[j + 1]:
                    row[j] *= 2
                    del row[j + 1]
            # Điền 0 vào cuối
            while len(row) < 4:
                row += [0]
            board[i] = row
        
        # Xoay ngược để khôi phục hướng
        if direction == "R":
            board = rot_anti_clock_dir(rot_anti_clock_dir(board))
        elif direction == "U":
            board = rot_anti_clock_dir(rot_anti_clock_dir(rot_anti_clock_dir(board)))
        elif direction == "D":
            board = rot_anti_clock_dir(board)
        
        return board

def rot_anti_clock_dir(x):
    """Xoay ma trận 4x4 ngược chiều kim đồng hồ 90 độ."""
    x = [[x[i][j] for i in range(4)] for j in range(4)]
    return x[::-1]

# Test
ob = Solution()
matrix = [
    [2, 0, 0, 2],
    [2, 2, 2, 2],
    [0, 4, 2, 2],
    [2, 2, 2, 0]
]
print(ob.solve(matrix, "L"))

Đầu vào:

matrix = [
    [2, 0, 0, 2],
    [2, 2, 2, 2],
    [0, 4, 2, 2],
    [2, 2, 2, 0]
]
direction = "L"

Đầu ra:

[
    [4, 0, 0, 0],
    [4, 4, 0, 0],
    [4, 4, 0, 0],
    [4, 2, 0, 0]
]