13. 机器人的运动范围

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution
{
    int getPositionSum(int row, int column)
    {
        int sum = 0;
        while(row > 0 || column > 0)
        {
            sum += row % 10 + column % 10;
            row /= 10;
            column /= 10;
        }

        return sum;
    }

    void move(int rows, int columns, int sum, int row, int column, unordered_set<int> &m_visitedGrid)
    {
        if(row < rows && column < columns && getPositionSum(row, column) <= sum && m_visitedGrid.find(row * 100 + column) == m_visitedGrid.end())
        {
            m_visitedGrid.insert(row * 100 + column);

            move(rows, columns, sum, row + 1, column, m_visitedGrid);
            move(rows, columns, sum, row, column + 1, m_visitedGrid);
        }
    }
public:
    // int movingCount(int m, int n, int k)
    int movingCount(int rows, int columns, int sum)
    {
        unordered_set<int> visitedGrid;
        move(rows, columns, sum, 0, 0, visitedGrid);

        return visitedGrid.size();
    }
};