本文共 1321 字，大约阅读时间需要 4 分钟。

剑指offer13. 机器人的运动范围 P92

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

// 判断当前访问的格子是不是有效// 参数：二维数组行，列总数，当前行，列索引，给定k值，访问标志bool isValid(int rows, int cols, int i, int j, int k, bool *visited) {
        if (i < 0 || i >= rows || j < 0 || j >= cols || visited[i * cols + j])         return false;     // 边界条件不满足，访问访问过	 int sum = 0;       // i，j的各位和	 while (i != 0) {
   	 	sum += i % 10;	 	i /= 10;	 }	 while (j != 0) {
   	 	sum += j % 10;	 	j /= 10;	 }	 if (sum > k) return false;  	 return true;}int countS(int rows, int cols, int i, int j, int k, bool *visited) {
    // 递归	int count = 0;	if (isValid(rows, cols, i, j, k, visited)) {
          //当前格满足条件 		visited[i * cols + j] = true;		count =  1 + countS(rows, cols, i - 1, j,  k, visited) //不是count += 			       + countS(rows, cols, i, j - 1,  k, visited) 			       + countS(rows, cols, i + 1, j,  k, visited) 			       + countS(rows, cols, i, j + 1,  k, visited);	}	return count;}int movingCount( int k, int rows, int cols) {
   	if (k < 0 || rows < 1 || cols < 1)   return 0;	bool *visited = new bool[rows * cols];	memset(visited, 0, rows * cols);	int ans = countS(rows, cols, 0, 0, k, visited);//不用再两层for遍历了 	delete []visited;    return ans; }

转载地址：http://bhzzi.baihongyu.com/