C++(BFS), Convert to a shortest path of an undirected graph


  • 1
    K
    class Solution {
    public:
        int numSquares(int n) {
            assert(n > 0);
            queue<pair<int, int>> q;
            vector<int> visted(n+1, 0);
            q.push(make_pair(n, 0));
            while(!q.empty()) {
                int num = q.front().first;
                int step = q.front().second;
                q.pop();
                for(int i = 1; ; i++) {
                    int a = num - i*i;
                    if(a == 0) return step + 1; 
                    if(a < 0) break;
                    if(!visted[a]) {
                        visted[a] = 1;
                        q.push(make_pair(a, step + 1));
                    }
                }
            }
            throw invalid_argument("No Solutions");
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.