剑指offer编程题—机器人的运动范围

题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

解题思路1
图的深度优先搜索思想：将方格矩阵看作一张图，矩阵中每个坐标点相当于图中的顶点，在不越界的情况下，每个坐标点可以向左，右，上，下四个方向移动一格，移动后到达的坐标点即相当于图中原顶点的临界点。
深度优先搜索的思想就是：从图中的一个顶点出发，每次遍历当前访问顶点的临界点，直到当前访问顶点没有未被访问的临界点为止，然后采用依次回退的方式，查看来的路上每一个顶点是否还有其他未被访问的临界点。
所以遍历之前需要设置一个全局数组，标记访问过的顶点。
图的深度优先搜索是一个不断回溯的过程。

/*题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是
不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7=18。
但是，它不能进入方格（35,38），因为3+5+3+8=19。请问该机器人能够达到多少个格子？
*/
#include<iostream>
#include<vector>
using namespace std;

class Solution {
    int boundary;  //阈值
    int m,n; //行列坐标
    vector<vector<bool> > visited; //标记数组，标记坐标是否被访问过
public:
    int movingCount(int threshold, int rows, int cols)
    {
        boundary=threshold;
        m=rows;
        n=cols;
        visited=vector<vector<bool> >(m,vector<bool>(n,false));
        return dfs(0,0);
    }

    //深度优先搜索
    int dfs(int x,int y){
        if(!ok(x,y)) return 0;
        visited[x][y]=true;
        int count=1;
        count+=dfs(x-1,y); //向左走
        count+=dfs(x+1,y); //向右走
        count+=dfs(x,y-1); //向下走
        count+=dfs(x,y+1); //向上走
        return count;
    }

    //(x,y)不越界，且没有被访问过，且(x,y)的数位和不超过threshold。
    bool ok(int x,int y){
        //注意C++中 a<=x<b 与 a<=x && x<b 是不等价的，下面注释点的写法是错误的。
        //return 0<=x<m && 0<=y<n && !visited[x][y] && fsum(x,y)<=boundary; 
        return x>=0 && x<m && y>=0 && y<n && !visited[x][y] && fsum(x,y)<=boundary;
    }

    //返回整数x，y的数位和
    int fsum(int x,int y){
        int r=0;
        while(x){
            r+=x%10;
            x/=10;
        }
        while(y){
            r+=y%10;
            y/=10;
        }
        return r;
    }
};

int main(int argc,char **argv)
{
    Solution sol;
    int res=sol.movingCount(18,13,12);
    cout<<res<<endl;
    return 0;
}

解题思路2
图的广度优先搜索思想，大概思路跟Solution1差不多，只不过这里用的是广度优先搜索。
基本思想：广度优先搜索类似于树的层析遍历，从图的一个顶点出发，遍历每一个顶点时，依次遍历该顶点的所有邻接顶点，然后再从这些邻接点出发，同样访问他们的邻接点。按照这样的过程，直到所有访问顶点的邻接点都被访问过为止。
广度有线搜索除了要设置全局数组，标记顶点是否被访问过之外，还要借助队列来记录本身已经访问当时邻接点没有被访问的顶点。

class Solution2 {
    int boundary;  //阈值
    int m,n; //行列坐标
    vector<vector<bool> > visited; //标记数组，标记坐标是否被访问过
    queue<pair<int,int> > q;
public:
    int movingCount(int threshold, int rows, int cols)
    {
        boundary=threshold;
        m=rows;
        n=cols;
        visited=vector<vector<bool> >(m,vector<bool>(n,false));
        return bfs(0,0);
    }

    //广度优先搜索
    int bfs(int x,int y){
        pair<int,int> temp;
        int count=0;
        if(ok(x,y)) visited[x][y]=true, q.push(make_pair(x,y)), ++count; //(x,y)已经被访问，但是其邻接点还没有被访问，故加入队列

        while(!q.empty()){
            temp=q.front();  //已经访问的顶点出队列
            q.pop();
            x=temp.first;
            y=temp.second;
            //依次访问该顶点的邻接点
            if(ok(x-1,y)) visited[x-1][y]=true, ++count, q.push(make_pair(x-1,y));
            if(ok(x+1,y)) visited[x+1][y]=true, ++count, q.push(make_pair(x+1,y));
            if(ok(x,y-1)) visited[x][y-1]=true, ++count, q.push(make_pair(x,y-1));
            if(ok(x,y+1)) visited[x][y+1]=true, ++count, q.push(make_pair(x,y+1));
        }
        return count;
    }

    //(x,y)不越界，且没有被访问过，且(x,y)的数位和不超过threshold。
    bool ok(int x,int y){
        //注意C++中 a<=x<b 与 a<=x && x<b 是不等价的，下面注释点的写法是错误的。
        //return 0<=x<m && 0<=y<n && !visited[x][y] && fsum(x,y)<=boundary; 
        return x>=0 && x<m && y>=0 && y<n && !visited[x][y] && fsum(x,y)<=boundary;
    }

    //返回整数x，y的数位和
    int fsum(int x,int y){
        int r=0;
        while(x){
            r+=x%10;
            x/=10;
        }
        while(y){
            r+=y%10;
            y/=10;
        }
        return r;
    }
};

C++踩坑

C++中 a<= x <=b与a<=x && x<=b是不等价的。

原因是a<= x <=b 等价于(a<=x) <= b,先进行左边的比较，再将左边的结果与右边进行比较。