口试题目67（机器人的运动范围）

面试题目67（机器人的运动范围）

题目：地上有一个M行N列的方格，一个机器人从坐标（0，0）的格子开始移动，它每一次可以向上下左右移动一格

，但不能进入行坐标和列坐标的数位之和大于k的格子，例如当k为18时，机器人能够进入方格（35，37），因为3+5+7+3=18

#include<iostream>
using namespace std;
int getdigitsum(int number)
{
	int sum=0;
	while(number>0)
	{
		sum+=number%10;
		number/=10;
	}
	return sum;
}
bool check(int threshold,int rows,int cols,int row,int col,bool *visited)
{
	if(row>=0&&row<rows&&col>=0&&col<cols&&(getdigitsum(row)+getdigitsum(col))<=threshold&&!visited[row*cols+col])
	{
		return true;
	}
	return false;
}
int movingcount_core(int threshold,int rows,int cols,int row,int col,bool *visited)
{
	int count=0;
	if(check(threshold,rows,cols,row,col,visited))
	{
		visited[row*cols+col]=true;
		count=1+movingcount_core(threshold,rows,cols,row,col-1,visited)
			+movingcount_core(threshold,rows,cols,row,col+1,visited)
			+movingcount_core(threshold,rows,cols,row-1,col,visited)
			+movingcount_core(threshold,rows,cols,row+1,col,visited);

	}
	return count;
}
int movingcount(int threshold,int rows,int cols)
{
	bool *visited=new bool[rows*cols];
	for(int i=0;i<rows*cols;++i)
	{
		visited[i]=false;
	}
	int count=movingcount_core(threshold,rows,cols,0,0,visited);
	delete [] visited;
	return count;
}
int main()
{
	int count=movingcount(4,4,4);
	cout<<count<<endl;
	system("pause");
	return 0;
}