Chương trình kiểm tra robot có thể đến đích bằng cách di chuyển trên ô đã thăm bằng Python

Robot bắt đầu tại tọa độ (0, 0) trên mặt phẳng Descartes. Cho danh sách các bước di chuyển gồm N (Bắc), S (Nam), W (Tây), E (Đông). Quy tắc đặc biệt: nếu robot đến ô đã từng thăm, nó sẽ tiếp tục di chuyển cùng hướng cho đến khi gặp ô chưa thăm. Cần kiểm tra sau chuỗi di chuyển robot có dừng tại tọa độ (x, y) cho trước hay không.

Ví dụ: moves = ['N','N','E','N','W','S'], coord = [0, -1] → True.

Quy trình giải quyết

1. Khởi tạo nx = ny = 0, tập visited = {(0, 0)}.
2. Với mỗi bước k trong moves:
   • Tùy hướng N/S/E/W, lặp while (nx, ny) in visited để tăng/giảm tọa độ cho đến khi tìm được ô mới.
   • Thêm ô mới vào visited.
3. Trả về True nếu (nx, ny) == coord, ngược lại False.

Ví dụ mã nguồn

class Solution:
    def solve(self, moves, coord):
        ny = nx = 0
        visited = {(0, 0)}
        for k in moves:
            if k == "N":
                while (nx, ny) in visited:
                    ny += 1
            elif k == "S":
                while (nx, ny) in visited:
                    ny -= 1
            elif k == "E":
                while (nx, ny) in visited:
                    nx += 1
            else:  # W
                while (nx, ny) in visited:
                    nx -= 1
            visited.add((nx, ny))
        return coord[0] == nx and coord[1] == ny

ob = Solution()
moves = ['N','N','E','N','W','S']
coord = [0, -1]
print(ob.solve(moves, coord))  # Output: True

Đầu vào

['N','N','E','N','W','S'], [0, -1]

Đầu ra

True