package main

import (
    "fmt"
    "os"
)

func readFile(filename string) [][]int{
    // 定義一個行和列,用來接收迷宮是幾行幾列的數組
    var row, col int
    file, e := os.Open(filename)
    if e != nil {
        panic("error")
    }
    defer file.Close()

    fmt.Fscan(file, row, col)

    // 定義一個數組
    // 注意: 定義數組的時候, 我們只要傳入幾行就可以了.
    // 二維數組的含義, 其實質是一個一維數組, 一維數組里每一個元素又是一個數組
    maze := make([][]int, row)
    for i := 0; i  len(maze); i++ {
        maze[i] = make([]int, col)
        for j := 0; j  len(maze[i]); j++ {
            fmt.Fscan(file, maze[i][j])
        }
    }

    return maze
}

type point struct {
    i, j int
}

// 當前節點, 向四個方向探索后的節點
// 這里使用的是返回新的節點的方式, 不修改原來的節點. 所以使用的是值拷貝,而不是傳地址
func (p point) add(dir point) point{
    return point{p.i + dir.i, p.j + dir.j }
}

// 獲取某個點的坐標值
// 同時判斷這個點有沒有越界, 返回的是這個值是否有效
// return 第一個參數表示返回的值是否是1, 是1表示撞墻了
//        第二個參數表示返回的值是否不越界, 不越界返回true, 越界,返回false 就和你
func (p point) at(grid [][]int) (int, bool) {
    if p.i  0 || p.i >= len(grid) {
        return 0, false
    }

    if p.j 0 || p.j >= len(grid[0]) {
        return 0, false
    }
    return grid[p.i][p.j], true
}

// 定義要探索的方向, 上下左右四個方向
var dirs = []point {
    point{-1, 0},
    point{0, -1},
    point{1, 0},
    point{0, 1},
}

// 走迷宮
func walk(maze [][]int, start, end point) [][]int {
    // 第一步: step代表從start開始, 走了多少步走到目標點, 最后的路徑是通過這個創建出來的, 最后從后往前推就可以算出最短路徑
    // 2. 通step還可以知道哪些點是到過的, 哪些點是沒到過的
    step := make([][]int, len(maze))
    for i := range step {
        // 定義每一行有多少列, 這樣就定義了一個和迷宮一樣的二維數組
        step[i] = make([]int, len(maze[i]))
    }

    // 第二步: 定義一個隊列, 用來保存已經發現還未探索的點, 隊列里的初始值是(0,0)點
    Que := []point{start}

    // 第三步: 開始走迷宮, 走迷宮退出的條件有兩個
    // 1. 走到終點, 退出
    // 2. 隊列中沒有元素, 退出
    for len(Que) > 0 {
        // 開始探索, 依次取出隊列中, 已經發現還未探索的元素
        // cur 表示當前要探索的節點
        cur := Que[0]
        // 然后從頭拿掉第一個元素
        Que = Que[1:]

        // 如果這個點是終點, 就不向下探索了
        if cur == end {
            break
        }

        // 當前節點怎么探索呢? 要往上下左右四個方向去探索
        for _, dir := range dirs {
            // 探索下一個節點, 這里獲取下一個節點的坐標. 當前節點+方向
            next := cur.add(dir)
            // 判斷坐標是否符合探索的要求
            // 1. maze at next is 0
            // 2. and setp at next is 0, 如果step的值不是0 ,說明曾經到過這個點了, 不能重復走
            // 3. next != start 處理特殊點, (0,0)點

            // 探索這個點是否是墻
            val, ok := next.at(maze)
            if !ok || val == 1 {
                continue
            }

            // 探索這個點是否已經走過
            val, ok = next.at(step)
            if val != 0 || !ok {
                continue
            }

            // 走到起始點了, 返回
            if next == start {
                continue
            }

            // 已經找到這個點了, 計算當前的步數
            curval, _ := cur.at(step) // 當前這一步的步數
            step[next.i][next.j] = curval + 1 // 下一步是當前步數+1
            Que = append(Que, next) // 將下一步節點放入到隊列中
        }

    }
    return step
}

func main() {

    maze := readFile("maze/maze.in")

    steps := walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1})
    // len(maze)-1, len[maze[0]]-1 是終點
    // 0,0是起始點
    for _, row := range steps {
        for _, val := range row  {
            fmt.Printf("%3d", val)
        }
        fmt.Println()
    }
}