数据结构与算法第一期:机器人的运动范围

机器人的运动范围:
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。---数据结构就是矩阵
一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外）， ---约束条件1 ：顺时针
也不能进入行坐标和列坐标的数位之和大于k的格子。 -----约束条件2:
例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。
但它不能进入方格 [35, 38]，因为3+5+3+8=19。
请问该机器人能够到达多少个格子？ -------结束条件怎么判断

var (
 visited [][]bool //元素第二次遍历需要回溯,防止重复遍历。很容易忘记
 rows    int
 cols    int
 sum     int
)

func movingCount(m int, n int, k int) int {
 //01 定义数据结构
 rows = m
 cols = n
 sum = k

 //go二维切片就是 int** 指针 vector<vector<bool>> 和java对象寓意是一样的。

 visited = make([][]bool, rows)

 for i := 0; i < rows; i++ {
  visited[i] =  make([]bool,cols)
 }

 //02 dfs遍历：不重复 不遗留
 
 return dfs(0,0);

}

func dfs(x int,y int) int {

 //约束条件1：
 if x <0 || x >=rows || y <0 || y >=cols {
  return 0//长度是0 相当于回溯返回了。进来--有走了
 }
    //约束条件2：
 if visited[x][y] == true {
  return 0 //重复元素不计算2次
 }
 //约束条件3：
 if get(x)+get(y) >sum {
  return 0
 }
 
 visited[x][y]  =true;

 return 1+dfs(x, y+1) + dfs(x+1, y)
}


 // 计算一个数的各个位数之和
 func  get(x int)  int{
  res := 0
 for x != 0 {
  res += x % 10
  x /= 10
 }
 return res
}

struct Points
{
  int x;
  int y;
  Points(int a,int b)
  {
 x =a;
 y =b; 
  }
};

class Solution 
{
 public:
  //广度优先搜索：利用队列实现
  //只要边和边关系，2个方向是可以遍历全部节点的。
  //A gossip protocol is a procedure or process of computer peer-to-peer communication that is based on the way epidemics spread
  int movingCount(int m, int n, int k) {

   //O1 定义数据结构
   queue<Points> bfsQueue;
   vector<vector<bool> > visited(m,vector<bool>(n,false)); // ？？？？？？
   // 向右和向下的方向数组
   int postion[2][2] ={{0,1},{1,0}};
   
   //02 初始化数据
   bfsQueue.push(Points(0,0)); 
   //void push (value_type&& val);
   visited[0][0] =true; //很容易忘记

   //03 遍历结束条件
         int total =0;
   while(!bfsQueue.empty())
   {
    
   //约束条件：
   //放入到队列数据都是，没有被重复遍历过数据。
   //可以拿出来直接使用,因此不㤇判断是否重复
   Points  cur = bfsQueue.front();
   bfsQueue.pop();  
  
   //遍历迭代过程
  
   for(int i=0;i<2;i++)
   {
    int nextX =cur.x +postion[i][0];
    int nextY =cur.y +postion[i][1];

    //约束条件：通过移动位置寻找邻居,这个是计算出来的。
    // 因为没有创建邻居表这样图结构。
    if (nextX < 0 || nextX >= m 
     || nextY < 0 || nextY >= n 
     || visited[nextX][nextY] ==true
     || get(nextX) + get(nextY) > k) 
    {
     continue;
    }    
    bfsQueue.push(Points(nextX,nextY)); 
    total++; //遍历过程中，统计个数
    visited[nextX][nextY] =true;//遗留了

   }
   }
   return total;

  }

  int get(int x) {
   int res=0;
   for (; x; x /= 10){
    res += x % 10;
   }
   return res;
  }
};