题解 | #迷宫问题#

package main

import (
    "fmt"
)

func dfs(matrix [][]int, row int, col int, visited [][]bool, path *[][2]int) bool {
    m, n := len(matrix), len(matrix[0])

    // 递归出口
    if row == m-1 && col == n-1 {
        *path = append(*path, [2]int{row, col})
        return true
    }

    if row<0 || row>=m || col<0 || col>=n || matrix[row][col] == 1 || visited[row][col] {
        return false
    }

    *path = append(*path, [2]int{row, col})
    visited[row][col] = true

    if dfs(matrix, row-1, col, visited, path) || dfs(matrix, row+1, col, visited, path) || dfs(matrix, row, col-1, visited, path) || dfs(matrix, row, col+1, visited, path) {
        return true
    }

    *path = (*path)[:len(*path)-1]
    visited[row][col] = false
    return false
}

func main() {
    var m, n int
    fmt.Scan(&m, &n)

    matrix := make([][]int, m)
    for i:=0; i<m; i++ {
        matrix[i] = make([]int, n)
    }

    for i:=0; i<m; i++ {
        for j:=0; j<n; j++ {
            var num int
            fmt.Scan(&num)
            matrix[i][j] = num
        }
    }

    visited := make([][]bool, m)
    for i:=0; i<m; i++ {
        visited[i] = make([]bool, n)
    }
    var path [][2]int
    dfs(matrix, 0, 0, visited, &path)

    for _, p := range path {
        fmt.Printf("(%d,%d)\n", p[0], p[1])
    }
}

// 本题输入为一个矩阵，所以采用 fmt.Scan(&m, &n)