题目描述

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

示例 1：

输入：m = 2, n = 3, k = 1
输出：3
示例 2：

输入：m = 3, n = 1, k = 0
输出：1
提示：

1 <= n,m <= 100
0 <= k <= 20

解题思路

以行为单位，依次遍历每一个方格，若方格满足被进入条件则将此网格进行标记。判断条件有如下：
1、一行的第一个方格，且行坐标和列坐标的数位之和不大于k；
2、该方格的上面方格或者左方方格被标记，且行坐标和列坐标的数位之和不大于k；
终止条件：某一行的所有方格都不能进入则终止。

代码

int movingCount(int m, int n, int k){
    int i, j, sum_i = 0, sum_j = 0, count_sum = 0, count_i = 0;
    int visited[m][n];

    for (i = 0; i < m; i++)
    {
        count_i = 0;
        sum_i = i / 10 + i % 10;
        for (j = 0; j < n; j++)
        {
            sum_j = j / 10 + j % 10;
            if(((j == 0) || ((j > 0) && (visited[i][j - 1] == 1)) || ((i > 0) && (visited[i - 1][j] == 1))) && (sum_i + sum_j <= k))
            {
                visited[i][j] = 1;
                count_i++;
            }
            else
            {
                visited[i][j] = 0;
            }
        }

        // 若其中某行没有任何一个满足条件的格子，则结束
        if(count_i == 0)
        {
            break;
        }
        else
        {
            count_sum += count_i;
        }
    }
    return count_sum;
}

测试代码及结果

#include<stdio.h>

int main(void)
{
    int count1, count2, count3, count4;

    // 功能测试
    count1 = movingCount(10, 10, 15);
    printf("%d\n", count1);
    count2 = movingCount(5, 4, 6);
    printf("%d\n", count2);

    // 边界值测试
    count3 = movingCount(5, 1, 2); // 多行一列
    printf("%d\n", count3);
    count4 = movingCount(1, 8, 5); // 一行多列
    printf("%d\n", count4);

    // 特殊输入测试
    count3 = movingCount(3, 3,-2); // k为负数
    printf("%d\n", count3);
}

执行代码

时间复杂度：O(n) = n^2，空间复杂度：O(1)。