机器人的运动范围

题目描述

地上有一个 m 行和 n 列的方格。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 k 的格子。例如，当 k 为18时，机器人能够进入方格 [35,37]，因为3+5+3+7=18。但是，它不能进入方格 [35,38]，因为3+5+3+8=19。请问该机器人能够达到多少个格子？

示例

输入:

5,10,10

输出：

21

数位之和

例如，123 的数位之和等于 1+2+3=6。计算某个数的数位之和代码如下所示：

/**
* 计算数位之和
*
* @param int $num 整型数
* @return int
*/
public function sum($num)
{
    $result = 0;
    while ($num) {
        $result += $num % 10;
        $num    = floor($num / 10);
    }
    return $result;
}

分析

蓝色格子表示机器人可到达。
由下面6张图可知，随着 k 值的变大，新加入的蓝色方格都可以由上方或左方的格子移动一步得到。最后其他不连通的蓝色方格区域会随着 k 的增大而连通，且连通的时候也是由上方或左方的格子移动一步得到，因此我们可以将我们的搜索方向缩减为向右或向下。

代码

<?php

namespace app\controller;

class Index
{
    /**
     * 机器人的运动范围
     *
     * @param int $threshold 阈值k
     * @param int $rows      行
     * @param int $cols      列
     * @return mixed
     */
    public function movingCount($threshold, $rows, $cols)
    {
        $col     = array_fill(0, $cols, 0);    // 初始化 $cols 个元素的一维数组
        $visited = array_fill(0, $rows, $col); // 初始化 $rows × $cols 个元素的二维数组

        return $this->DFS(0, 0, $rows, $cols, $visited, $threshold);
    }

    /**
     * 深度遍历
     *
     * @param int   $i         当前行
     * @param int   $j         当前列
     * @param int   $rows      总行数
     * @param int   $cols      总列数
     * @param array $visited   二维数组
     * @param int   $threshold 阈值k
     * @return int
     */
    public function DFS($i, $j, $rows, $cols, &$visited, $threshold)
    {
        // 如果： 超过行数 || 超过列数 || 数位之和大于阈值 || 格子已遍历过
        if ($i>=$rows || $j>=$cols || $this->sum($i)+$this->sum($j) > $threshold || $visited[$i][$j])
            return 0;

        // 1 标记格子已遍历过
        $visited[$i][$j] = 1;

        return $this->DFS($i + 1, $j, $rows, $cols, $visited, $threshold)// $i+1：往当前格子的下边走一步
            + $this->DFS($i, $j + 1, $rows, $cols, $visited, $threshold) // $j+1：往当前格子的右边走一步
            + 1;
    }

    /**
     * 计算数位之和
     *
     * @param int $num 整型数
     * @return int
     */
    public function sum($num)
    {
        $result = 0;
        while ($num) {
            $result += $num % 10;
            $num    = floor($num / 10);
        }
        return $result;
    }
}

笔记

array_fill(int $start_key, int $num, mixed $value)：用给定的值填充数组

$start_key：键开始的值
$num：填充 $num 个
$value：填充的值