class Solution
{
public:
    int numSquares(int n)
    {
        queue<pair<int, int> > pq; //队列中放置一组数据
        vector<bool> used(n + 1, false);
        pq.push(make_pair(n, 0));

        while (!pq.empty())
        {
            int num = pq.front().first;
            int step = pq.front().second;

            pq.pop();
            for (int i = 1; num - i * i >= 0; ++i)
            {
                int a = num - i * i;
               
                if (a == 0)
                {
                    return step + 1;   //一旦发现为空就立即返回，因为先为空的它的层数自然也最少
                }
                if (a > 0)
                {
                    if (!used[a])
                    {
                        pq.push(make_pair(a, step + 1));
                        used[a] = true;
                    }
                }
            }
        }
        return 0;
    }
};