剑指 Offer 13. 机器人的运动范围

题目

剑指 Offer 13. 机器人的运动范围

我的思路

广度搜索+记忆化矩阵

时间复杂度和空间复杂度都是m*n。

我的实现

class Solution {
public:
    int calculate(int n){
        int s = 0;
        for(;n>0;n=n/10){
            s = n%10+s;
        }
        return s;
    }
    int movingCount(int m, int n, int k) {
        //广搜
        //初始化一个队列、记忆搜索矩阵
        vector<bool> initializer(n,false);
        vector<vector<bool>> memoryMatrix(m,initializer);
        queue<pair<int,int>> searchingQ;
        
        //插入队头（0,0）
        int sum = 0;
        pair<int,int> base(0,0);
        
        searchingQ.push(base);
        //遍历队头：
        pair<int,int> temp;
        while(!searchingQ.empty()){
            //取出队头
            temp = searchingQ.front();//指针对象引用的关系到底是怎样？？
            searchingQ.pop();
            //看未走过的临近方格是否满足要求（在地图内，数字和小于k），若满足把它加入队尾、总计数+1、标记为已走过
            if((temp.first+1<m)&&(calculate(temp.first+1)+calculate(temp.second)<=k)&&memoryMatrix[temp.first+1][temp.second]==false){
                memoryMatrix[temp.first+1][temp.second] = true;
                pair<int,int>temp1 = pair<int,int>(temp.first+1,temp.second);
                searchingQ.push(temp1);
            }
            if((temp.second+1<n)&&(calculate(temp.first)+calculate(temp.second+1)<=k)&&memoryMatrix[temp.first][temp.second+1]==false){
                memoryMatrix[temp.first][temp.second+1] = true;
                pair<int,int>temp2 = pair<int,int>(temp.first,temp.second+1);
                searchingQ.push(temp2);
            }
            sum++;
        }
        return sum;
    }
};

/*
queue与vector***
pair类模板
*/


/*
    0-9,1-10,2-11,...,9-18,1
0-9
1-10
2-11
...
9-18
1

8,9,10,11,12
仅仅依次扫描每一行并不能会漏掉一些可以抵达的方格
我没有仔细思考清楚一些情况
最好还是要借助一个辅助数组来存储已遍历的情况
*/

拓展学习

queue与vector***

 

http://c.biancheng.net/view/479.html

pair类模板

https://blog.csdn.net/sevenjoin/article/details/81937695