"""BTVN: tìm một/tất cả đường đi đơn trong mê cung, Python3.

python3 g11-cs-me-cung.py g11-cs-me-cung.inp --output maze.out
python3 g11-cs-me-cung.py g11-cs-me-cung.inp --giua --danh-tuong --output giua.out
python3 g11-cs-me-cung.py g11-cs-me-cung-nho.inp --tat-ca
x là cột, y là hàng; ô đọc bằng maze[y][x]; thử phải, xuống, trái, lên.
"""
import argparse
from pathlib import Path

npaths = 0


def readmaze(path):
    maze = []
    with open(path, encoding='utf-8') as file:
        for line in file:
            row = [int(value) for value in line.split()]
            if not row or any(value not in (0, 1) for value in row):
                raise ValueError('Mỗi dòng cần có các số0 hoặc1, cách nhau bởi dấu cách.')
            maze.append(row)
    if not maze or any(len(row) != len(maze[0]) for row in maze):
        raise ValueError('Mê cung cần là ma trận chữ nhật khác rỗng.')
    return maze


def writemaze(outmaze, path):
    with open(path, 'w', encoding='utf-8') as file:
        for row in outmaze:
            print(*row, file=file)


def printmaze(outmaze):
    for row in outmaze:
        print(*row)


def wall_view(maze, sol, mark_walls=False):
    return [['x' if mark_walls and maze[y][x] == 1 else sol[y][x]
             for x in range(len(row))] for y, row in enumerate(maze)]


def solveMaze(maze, m, n, x, y, sol, goals=None):
    if not (0 <= x < n and 0 <= y < m):
        return False
    if maze[y][x] != 0 or sol[y][x] == 1:
        return False
    if goals is None:
        goals = {(n - 1, m - 1)}
    sol[y][x] = 1
    if (x, y) in goals:
        return True
    for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        if solveMaze(maze, m, n, x + dx, y + dy, sol, goals):
            return True
    sol[y][x] = 0
    return False


def allMaze(maze, m, n, x, y, sol, path, goals=None, mark_walls=False):
    global npaths
    if not (0 <= x < n and 0 <= y < m):
        return
    if maze[y][x] != 0 or sol[y][x] == 1:
        return
    if goals is None:
        goals = {(n - 1, m - 1)}
    sol[y][x] = 1
    path.append((x, y))
    if (x, y) in goals:
        npaths += 1
        print(f'Đường {npaths}: {path}')
        printmaze(wall_view(maze, sol, mark_walls))
    else:
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            allMaze(maze, m, n, x + dx, y + dy, sol, path, goals, mark_walls)
    path.pop()
    sol[y][x] = 0


def main():
    global npaths
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument('input', type=Path)
    parser.add_argument('--output', type=Path)
    parser.add_argument('--giua', action='store_true')
    parser.add_argument('--danh-tuong', action='store_true')
    parser.add_argument('--tat-ca', action='store_true')
    args = parser.parse_args()
    try:
        maze = readmaze(args.input)
        m, n = len(maze), len(maze[0])
        if m * n > (16 if args.tat_ca else 60):
            raise ValueError('Bản thực hành nhận tối đa60 ô; chế độ tất cả nhận tối đa16 ô.')
        x, y = (n // 2, m // 2) if args.giua else (0, 0)
        goals = {(0, 0), (n - 1, m - 1)} if args.giua else {(n - 1, m - 1)}
        sol = [[0 for _ in range(n)] for _ in range(m)]
        print(f'Kích thước: {m} hàng, {n} cột; xuất phát ({x}, {y}).')
        if args.tat_ca:
            if args.output:
                raise ValueError('Chế độ tất cả in ra màn hình, không nhận --output.')
            npaths = 0
            allMaze(maze, m, n, x, y, sol, [], goals, args.danh_tuong)
            print('Tổng số đường:', npaths)
        else:
            out = args.output or Path('maze.out')
            if args.input.resolve() == out.resolve():
                raise ValueError('Tệp kết quả phải khác tệp đầu vào.')
            found = solveMaze(maze, m, n, x, y, sol, goals)
            result = wall_view(maze, sol, args.danh_tuong) if found else []
            writemaze(result, out)
            if found:
                print('Đường đi tìm được:')
                printmaze(result)
            else:
                print('Không tồn tại đường đi; tệp kết quả rỗng.')
    except (OSError, ValueError) as error:
        parser.exit(2, f'Dữ liệu không phù hợp: {error}\n')


if __name__ == '__main__':
    main()