6. 迷宮遊戲

namespace Q6
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }


        private void button1_Click(object sender, EventArgs e)
        {
            var maze = File.ReadAllText(textBox1.Text).Split("\n").Select(r => r.Split(' ').Select(r => int.Parse(r)).ToArray()).ToArray();
            find = false;
            ans.Clear();
            bt(maze, 0, 0, []);

            textBox2.Text = string.Join("", ans.Select(r => $"({r.Y},{r.X})"));
        }

        bool find = false;
        List<Point> ans = new();

        void bt(int[][] maze, int x, int y, List<Point> path)
        {
            if (x < 0 || y < 0 || x > 7 || y > 7) return;
            if (maze[y][x] != 0) return;

            if (path.Any(p => p.X == x & p.Y == y)) return;
            if (find) return;

            path.Add(new Point(x, y));
            if (!ans.Any(r => r.X == x && r.Y == y)) ans.Add(new Point(x, y));

            if (x == 7 && y == 7)
            {
                find = true;
                return;
            }

            bt(maze, x, y - 1, path);     // N
            bt(maze, x + 1, y - 1, path); // NE
            bt(maze, x + 1, y, path);     // E
            bt(maze, x + 1, y + 1, path); // SE
            bt(maze, x, y + 1, path);     // S
            bt(maze, x - 1, y + 1, path); // SW
            bt(maze, x - 1, y, path);     // W
            bt(maze, x - 1, y - 1, path); // NW

            // 回溯：移除最後一步
            path.RemoveAt(path.Count - 1);
        }

    }
}