C++ Code (Based on 2d prefix sum technique)
Intuition:\nFirst of all, we look at the constraints,.. and we see that a cubic solution will also be accepted.\nSo, we try to brute force through all the sizes
Intuition:\nFirst of all, we look at the constraints,.. and we see that a cubic solution will also be accepted.\nSo, we try to brute force through all the sizes of squares(size of a square is it\'s side length) possible and try to find out the number of squares of each size,.. now our answer will be the sum of all these.\n\nSo, the max possible size of a square is min(n,m). hence we run a loop from 1 to min(n,m).. Suppose we are calculating the number of squares of the size k,.. hence we need to check all the squares of size k,.. and if any of them is a valid one,.. then we add 1 to the answer,..\n\nSo the only question remains,.. given the vertices of a submatrix within a matrix,.. how do we efficiently check if it consists only of 1s,.. This can be easily achieved by using a matrix pref,.. such that pref[i][j] gives the sum of the submatrix whose leading daigonal\'s endpoints are 0,0 and i,j... This can be easily built by using the formula:\npref[i][j] = pref[i][j]+(pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1])\n\nwhere pref[i][j] has the values of the original matrix initally.(Look at the code to get a better understading)\nNow, once we have built this,..we can find out the sum for a submatrix whose leading diagonal\'s endpoints are (a,b) and (c,d) by using this formula:\n\nsum[(a,b],[c,d]) = pref[c][d]+pref[a-1][b-1]-(pref[c][b-1]+pref[a-1][d])\n\nThis is the idea I have implemented in the code below:\n```\ntypedef long long ll;\nclass Solution {\npublic:\n    bool issafe(ll x, ll y, ll n, ll m)\n    {\n        return (((0<=x)&&(x<=n))&&((0<=y)&&(y<=m)));\n    }\n    int countSquares(vector<vector<int>>& matrix) {\n        ll n = matrix.size();\n        ll m = matrix[0].size();\n        vector<vector<ll>> pref(n+1, vector<ll>(m+1,0));\n        for(ll i=1;i<=n;i++)\n        {\n            for(ll j=1;j<=m;j++)\n            {\n                pref[i][j] = matrix[i-1][j-1];\n            }\n        }\n        for(ll i=1;i<=n;i++)\n        {\n            for(ll j=1;j<=m;j++)\n            {\n                pref[i][j] += (pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1]);\n            }\n        }\n        ll max_sz = min(n,m);\n        ll res=0;\n        for(ll sz = 1; sz<= max_sz; sz++)\n        {\n            for(ll i=1;i<=n;i++)\n            {\n                for(ll j=1;j<=m;j++)\n                {\n                    ll a = i;\n                    ll b = j;\n                    ll c = i+sz-1;\n                    ll d = j+sz-1;\n                    if(issafe(c,d,n,m))\n                    {\n                        ll sum = pref[c][d]+pref[a-1][b-1]-(pref[c][b-1]+pref[a-1][d]);\n                        if(sum==(sz*sz))\n                        {\n                            res++;       \n                        }    \n                    }\n                    \n                }\n            }\n        }\n        return res;\n    }\n};\n```\nTC:O(n\xB3)\nAuxiliary space: O(n\xB2)\nps: This is less optimal than the dp based approach which runs in O(n\xB2) time.
['C', 'Matrix']