下面要给大家分享的是回溯法-机器人的运动范围的代码实现和思路，具体介绍了3种代码实现方式思路。

题目：

地面上有一个m行和n列的方格，机器人从坐标0,0的格子开始进行一栋，每次，只能向左，右，上，下四个方向移动一格，可是不能够进入行坐标和列坐标的数位之和大于k的格子。

例：

在k是18时，机器人可以进入方格(35,37)，因为3+5+3+7=18。

可是，机器人不能够进入方格(35,38)，因为3+5+3+8=19。

问：

机器人可以达到多少个格子?

思路1

代码实现：

class Solution
{
    bool canreach(int threshold, int x, int y)
    {
        int sum = 0;
        while (x > 0)
        {
            sum += x % 10;
            x /= 10;
        }
        while (y > 0)
        {
            sum += y % 10;
            y /= 10;
        }
        return sum <= threshold;
    }
    public:
        int movingCount(int threshold, int rows, int cols)
        {
            vector < vector < bool >> grid(rows);
            for (auto & row: grid)
            {
                row.resize(cols, false);
            }
            queue < pair < int, int >> que;
            if (canreach(threshold, 0, 0))
            {
                que.push(make_pair(0, 0));
                grid[0][0] = true;
            }
            int cnt = 0;
            while (!que.empty())
            {
                ++cnt;
                int x, y;
                tie(x, y) = que.front();
                que.pop();
                if (x + 1 < rows && !grid[x + 1][y] && canreach(threshold, x + 1, y))
                {
                    grid[x + 1][y] = true;
                    que.push(make_pair(x + 1, y));
                }
                if (y + 1 < cols && !grid[x][y + 1] && canreach(threshold, x, y + 1))
                {
                    grid[x][y + 1] = true;
                    que.push(make_pair(x, y + 1));
                }
            }
            return cnt;
        }
};

思路2：

动态规划dp[i][j]表示是不是可以到达，统计数字中true的个数，即为可以到达的格子数。

代码实现：

public class Solution
{
    public int movingCount(int threshold, int rows, int cols)
    {
        if (threshold < 0)
            return 0;
        boolean[][] dp = new boolean[rows + 1][cols + 1];
        dp[0][0] = true;
        for (int i = 1; i <= rows; i++)
        { //初始化
            if (dp[i - 1][0] && canreach(threshold, i, 0))
            {
                dp[i][0] = true;
            }
            else
            {
                dp[i][0] = false;
            }
        }
        for (int i = 1; i <= cols; i++)
        { //初始化
            if (dp[0][i - 1] && canreach(threshold, 0, i))
            {
                dp[0][i] = true;
            }
            else
            {
                dp[0][i] = false;
            }
        }
        for (int i = 1; i <= rows; i++)
        {
            for (int j = 1; j <= cols; j++)
            {
                if ((dp[i - 1][j] && canreach(threshold, i, j)) || (dp[i][j - 1] && canreach(threshold, i, j)))
                {
                    dp[i][j] = true;
                }
                else
                {
                    dp[i][j] = false;
                }
            }
        }
        int count = 0;
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                if (dp[i][j])
                    count++;
            }
        }
        return count;
    }
    public boolean canreach(int threshold, int x, int y)
    {
        int sum = 0;
        while (x > 0)
        {
            sum += x % 10;
            x /= 10;
        }
        while (y > 0)
        {
            sum += y % 10;
            y /= 10;
        }
        return sum <= threshold;
    }
}

思路3

代码实现：

public class Solution
{
    public int movingCount(int threshold, int rows, int cols)
    {
        int[][] flag = new int[rows][cols];
        return moving(threshold, rows, cols, flag, 0, 0);
    }
    public int moving(int threshold, int rows, int cols, int[][] flag, int i, int j)
    {
        if (threshold <= 0 || i >= rows || i < 0 || j >= cols || j < 0 || (flag[i][j] == 1) || (sum(i) + sum(j) > threshold))
        {
            return 0;
        }
        flag[i][j] = 1;
        return moving(threshold, rows, cols, flag, i - 1, j) +
            moving(threshold, rows, cols, flag, i + 1, j) +
            moving(threshold, rows, cols, flag, i, j - 1) +
            moving(threshold, rows, cols, flag, i, j + 1) +
            1;
    }
    public int sum(int i)
    {
        if (i == 0)
        {
            return i;
        }
        int sum = 0;
        while (i != 0)
        {
            sum += i % 10;
            i /= 10;
        }
        return sum;
    }
}

以上的三种实现方式大家都了解了吗?具体的可以参考一下，更多Java实例，请继续关注本站了解吧!