剑指 Offer 13. 机器人的运动范围

水题一道，bfs

class Solution {
public:
    int vis[110][110];
    int dis[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    
    int cal(int x)
    {
        int sum = 0;
        while(x)
        {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }



    void bfs(int &cnt, const int &m, const int &n, const int &k)
    {
        queue<pair<int, int> > Q;
        Q.push(pair<int, int> (0, 0));
        vis[0][0] = 1;
        cnt++;
        while(!Q.empty())
        {
            pair<int, int> u = Q.front(); Q.pop();
            for(int i = 0; i < 4; i++)
            {
                int vx = u.first + dis[i][0];
                int vy = u.second + dis[i][1];
                if(vx < 0 || vy < 0 || vx >= m || vy >= n || vis[vx][vy] || cal(vx) + cal(vy) > k) continue;
                vis[vx][vy] = 1;
                cnt++;
                Q.push(pair<int, int> (vx, vy));
            }

        }

    }

    int movingCount(int m, int n, int k) {
        memset(vis, 0, sizeof(vis));
        int cnt = 0;
        bfs(cnt, m, n, k);
        return cnt;
    }
};