题解 | #机器人的运动范围#

从[0,0]开始向右或向下进行探索，直到不满足threshold就停止。

停止理由是如果当前坐标都不满足threshold，那么右下方就不可能有满足的坐标。

class Solution {
public:
    char ** newMaxtrix(int rows, int cols)
	{
		char **pp = new char *[rows];
		for (int i = 0; i < rows; ++i)
		{
			pp[i] = new char[cols];
			memset(pp[i], 0, cols);
		}
		
		return pp;
	}
	
	int sumDigit(int num)
	{
		int s = 0;
		while (num)
		{
			s += num % 10;
			num /= 10;
		}
		
		return s;
	}
	
	int search(int threshold, int rows, int cols, char **ppMatrix, int x, int y)
	{
		if (x >= rows || y >= cols)
		{
			return 0;
		}
		
		if (ppMatrix[x][y] == 1)
		{
			return 0;
		}
		
		int cnt = 0;
		if (sumDigit(x) + sumDigit(y) <= threshold)
		{
			ppMatrix[x][y] = 1;
			cnt++;
			cnt += search(threshold, rows, cols, ppMatrix, x + 1, y);
			cnt += search(threshold, rows, cols, ppMatrix, x, y + 1);
		}
		
		return cnt;
	}
	
    int movingCount(int threshold, int rows, int cols)
    {
		if (rows < 0 || cols < 0)
		{
			return 0;
		}
		
        char **ppMatrix = newMaxtrix(rows + 1, cols + 1);
		int cnt = search(threshold, rows, cols, ppMatrix, 0, 0);
		
		for (int i = 0; i < rows; i++)
		{
			delete ppMatrix[i];
		}
		
		delete ppMatrix;
		
		return cnt;
    }
};