机器人的运动范围

机器人的运动范围

http://www.nowcoder.com/questionTerminal/6e5207314b5241fb83f2329e89fdecc8

1、分治思想
f(i, j) = 1 + f(i - 1, j) + f(i + 1, j) + f(i, j - 1) + f(i, j + 1)

1、f(i, j)入参判断是否有效
2、是否重复

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        bool visited[rows * cols];
        for (int i = 0; i < rows * cols; i++) {
            visited[i] = false;
        }
        return MovingCore(0, 0, rows, cols, visited, threshold);
    }

    int MovingCore(int i, int j, int rows, int cols, bool *visited, int threshold)
    {
        if (i >= rows || i < 0 || j >= cols || j < 0) {
            return 0;
        }
        if (GetSum(i) + GetSum(j) > threshold) {
            return 0;
        }
        if (visited[i * cols + j]) {
            return 0;
        }
        visited[i * cols + j] = true;
        return 1 + MovingCore(i - 1, j, rows, cols, visited, threshold) +
               MovingCore(i + 1, j, rows, cols, visited, threshold) +
               MovingCore(i, j - 1, rows, cols, visited, threshold) +
               MovingCore(i, j + 1, rows, cols, visited, threshold);
    }

    int GetSum(int num)
    {
        int count = 0;
        while (num > 0) {
            count = count + num % 10;
            num = num / 10;
        }
        return count;
    }
};
全部评论

相关推荐

05-19 19:57
蚌埠学院 Python
2237:Gpa70不算高,建议只写排名,个人技能不在多而在精,缩到8条以内。项目留一个含金量高的,减少间距弄到一页,硕士简历也就一页,本科不要写很多
实习,投递多份简历没人回...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务