題目描述

地上有一個(gè)m行n列的方格，從坐標(biāo) [0,0] 到坐標(biāo) [m-1,n-1] 。一個(gè)機(jī)器人從坐標(biāo) [0, 0] 的格子開始移動，它每次可以向左、右、上、下移動一格（不能移動到方格外），也不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。例如，當(dāng)k為18時(shí)，機(jī)器人能夠進(jìn)入方格 [35, 37] ，因?yàn)?+5+3+7=18。但它不能進(jìn)入方格 [35, 38]，因?yàn)?+5+3+8=19。請問該機(jī)器人能夠到達(dá)多少個(gè)格子？

示例 1：

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

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

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

解題思路

以行為單位，依次遍歷每一個(gè)方格，若方格滿足被進(jìn)入條件則將此網(wǎng)格進(jìn)行標(biāo)記。判斷條件有如下：
1、一行的第一個(gè)方格，且行坐標(biāo)和列坐標(biāo)的數(shù)位之和不大于k；
2、該方格的上面方格或者左方方格被標(biāo)記，且行坐標(biāo)和列坐標(biāo)的數(shù)位之和不大于k；
終止條件：某一行的所有方格都不能進(jìn)入則終止。

代碼

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;
            }
        }

        // 若其中某行沒有任何一個(gè)滿足條件的格子，則結(jié)束
        if(count_i == 0)
        {
            break;
        }
        else
        {
            count_sum += count_i;
        }
    }
    return count_sum;
}

測試代碼及結(jié)果

#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為負(fù)數(shù)
    printf("%d\n", count3);
}

執(zhí)行代碼

時(shí)間復(fù)雜度：O(n) = n^2，空間復(fù)雜度：O(1)。