【剑指offor】面试题13：机器人的运动范围

题目描述

代码

class Solution {public:int sums(int x){//先把数位和的这个函数写出来int s = 0;while(x != 0) {s += x % 10;x = x / 10;}return s;}int check (int k,int rows,int cols, int row,int col,bool* visited){//检查当前坐标是否满足题意if(row >= 0 && row < rows && col >= 0 && col < cols&& sums(row) + sums(col) <= k&& !visited[row* cols + col])return true;return false;}int movingCount(int m, int n, int k) {if(k<0||m<=0||n<=0){return 0;}bool *visited = new bool[m*n];for(int i=0;i<n*m;i++){visited[i]=false;//全局的visited数组来判断这个坐标是否被访问过}int count = countcore(k,m,n,0,0,visited);delete[] visited;return count;}int countcore(int k,int m,int n,int row,int col,bool* visited){int count=0;if(check(k,m,n,row,col,visited)){visited[row*n+col] = true;count= 1+countcore(k,m,n,row-1,col,visited)+countcore(k,m,n,row+1,col,visited)+countcore(k,m,n,row,col-1,visited)+countcore(k,m,n,row,col+1,visited);}return count;//这个题目和找路径的题目还不太一样，这个不需要回溯，一条道走到黑，统计count就可以了。}};