剑指 Offer 13. 机器人的运动范围

https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

第一反应是回溯，写出来以后才发现是简单递归。回溯一般是用在穷举所有可能性时。

var res int
var visited [][]bool

func movingCount(m int, n int, k int) int {
    res = 0
    visited = make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    traverse(m, n, 0, 0, k)
    return res
}

func traverse(m, n, i, j, k int) {
    if i < 0 || i == m || j < 0 || j == n {
        return
    }

    if i / 10 + i % 10 + j / 10 + j % 10 > k {
        return
    }

    if visited[i][j] == false {
        visited[i][j] = true
        res++
    } else {
        return
    }

    traverse(m, n, i+1, j, k)
    traverse(m, n, i, j+1, k)
}