剑指offer 12.机器人的运动范围

机器人的运动范围

地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。

一个机器人从坐标 (0,0) 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于 k 的格子。

请问该机器人能够达到多少个格子？

样例1
输入：k=7, m=4, n=5

输出：20
样例2
输入：k=18, m=40, n=40

输出：1484

解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
      但是，它不能进入方格（35,38），因为3+5+3+8 = 19。
注意:

0<=m<=50
0<=n<=50
0<=k<=100

class Solution {
public:
	int get_simple_sum(int n)
	{
		int s=0;
		while(n)
		{
			s+=n%10;
			n/=10;
		}
		return s;
	}
	int get_sum(pair<int,int> p)
	{
		return get_simple_sum(p.first)+get_simple_sum(p.second);
	}
    int movingCount(int threshold, int rows, int cols)
    {
    	int res=0;
    	if(!rows||!cols)
        	return 0;
    	vector< vector<bool> > st(rows,vector<bool>(cols));
    	queue<pair<int,int> > q;
    	q.push({0,0});
    	int dx[4]={0,1,0,-1};
    	int dy[4]={-1,0,1,0};
    	while(q.size())
    	{
    		auto t=q.front();
    		q.pop();
    		if(get_sum(t)>threshold||st[t.first][t.second])
    			continue;
    		res++;
    		st[t.first][t.second]=true;
    		for(int i=0;i<4;i++)
    		{
    			int a=t.first+dx[i];
    			int b=t.second+dy[i];
    			if(a>=0 &&a<rows && b>=0 &&b<cols)
    				q.push({a,b});
    		}

    	}
    	return res;
    }
};