题解 | #迷宫问题#

package main

import (
	"fmt"
	"io"
)

func dfs(flag [1000][1000]bool, input [][]int, ret *[][]int, i, j, m, n int) {
	if i < 0 || j < 0 || i >= m || j >= n {
		return
	}
	if i == m-1 && j == n-1 {
		for i := range *ret {
			fmt.Printf("(%d,%d)\n", (*ret)[i][0], (*ret)[i][1])
		}
		fmt.Printf("(%d,%d)\n", m-1, n-1)
		return
	}
	if input[i][j] == 1 {
		return
	}
	if flag[i][j] {
		return
	}
	flag[i][j] = true
	*ret = append(*ret, []int{i, j})
	dfs(flag, input, ret, i-1, j, m, n)
	dfs(flag, input, ret, i+1, j, m, n)
	dfs(flag, input, ret, i, j-1, m, n)
	dfs(flag, input, ret, i, j+1, m, n)
	*ret = (*ret)[:len(*ret)-1]
	flag[i][j] = false
}
func main() {
	for {
		var (
			m, n int
		)
		var flag [1000][1000]bool
		_, err := fmt.Scanf("%d %d", &m, &n)
		if err == io.EOF {
			return
		}
		r := make([][]int, m)
		for i := range r {
			r[i] = make([]int, n)
		}
		for i := 0; i < m; i++ {
			for j := 0; j < n; j++ {
				fmt.Scan(&r[i][j])
			}
		}
		var ret [][]int
		dfs(flag, r, &ret, 0, 0, m, n)
	}
}