题目描述

地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。

一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于 k 的格子。

请问该机器人能够达到多少个格子？

golang 代码

//本题用广度优先搜索，不能用直接遍历判断节点（比如限制为3，点[10][10]也会被加进去）
type Queue struct{
    top         int
    bottom      int
    que         [][2]int
}

func movingCount(threshold, rows, cols int) int {
    if rows == 0 || cols == 0 {
        return 0
    }
    //新建二维Bool判断位置信息
    var address = make([][]bool,50)
    for i := 0 ; i < 50 ; i++ {
        address[i] = make([]bool,50)
    }
    //初始化队列
    myque := Queue{top:0,bottom:0,que:make([][2]int,5000)}
    var count int

    //首元素进队列
    myque.que[myque.top] = [2]int{0,0}
    myque.top++
    address[0][0] = true

    x := []int{1,-1,0,0}
    y := []int{0,0,1,-1}

    //队列非空
    for myque.top > myque.bottom {
        q := myque.que[myque.bottom]
        myque.bottom++
        count++
        //对队列四周元素遍历，如存在且可走，入队列
        for i := 0 ; i < 4 ; i++ {
            a := q[0] + x[i]
            b := q[1] + y[i]
            if a >= 0 && a < rows && b >= 0 && b < cols && getsum(a,b) <= threshold && address[a][b] == false {
                myque.que[myque.top] = [2]int{a,b}
                myque.top++
                address[a][b] = true
            }
        }
    }
    return count
}

func getsum(rows, cols int) int {
    return rows / 10 + rows % 10 + cols / 10 + cols % 10
}