在M x N大小的格网上随机生成自回避多边形

import random

def is_valid_move(x, y, M, N, visited):
    return 0 <= x < M and 0 <= y < N and not visited[x][y]

def generate_self_avoiding_polygon(M, N):
    visited = [[False] * N for _ in range(M)]
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # Right, Down, Left, Up
    
    # Start at a random point
    x, y = random.randint(0, M-1), random.randint(0, N-1)
    visited[x][y] = True
    path = [(x, y)]
    
    while True:
        next_moves = []
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if is_valid_move(nx, ny, M, N, visited):
                next_moves.append((nx, ny))
        
        if not next_moves:
            break
        
        nx, ny = random.choice(next_moves)
        visited[nx][ny] = True
        path.append((nx, ny))
        x, y = nx, ny
        
        # Check if we have returned to the start
        if (x, y) == path[0] and len(path) > 3:
            break
    
    return path

# Example usage
M, N = 10, 10
polygon = generate_self_avoiding_polygon(M, N)
print(polygon)