[C++] Easy Solution (DP/DFS)
In this particular post at first we look at the raw code which is essentially the same as the shorter version. This will help us understand the code better. \n\
In this particular post at first we look at the raw code which is essentially the same as the shorter version. This will help us understand the code better. \n\n**Algorithm**\n\nFor each (cardinal) direction, and for each coordinate (r, c) let\'s compute the count of that coordinate: the longest line of \'1\'s starting from (r, c) and going in that direction. With dynamic programming, it is either 0 if **grid[r][c]** is zero, else it is 1 plus the count of the coordinate in the same direction. For example, if the direction is left and we have a row like 01110110, the corresponding count values are 01230120, and the integers are either 1 more than their successor, or 0. For each square, we want **grid[r][c]** to end up being the minimum of the 4 possible counts. At the end, we take the maximum value in dp.\n\n\nTime Complexity: *O(N^2)*, as the work we do under two nested for loops is O(1)O(1).\nSpace Complexity: *O(N^2)*, the size of grid.\n\n![image](https://assets.leetcode.com/users/images/e361ae4a-9f95-46ba-8f3a-af5564aedebf_1631196300.6386557.png)\n\n\n**C++ DP Raw Version**\n```\nclass Solution {\npublic:\n    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {\n        vector<vector<int>>grid(n,vector<int>(n,n));\n        \n        for(auto m:mines){\n            grid[m[0]][m[1]]=0;\n        }\n        \n        for(int i=0;i<n;i++){\n            \n            \n            for(int j=0,left=0;j<n;j++){\n                if(grid[i][j]==0)left=0;\n                else left+=1;\n                grid[i][j]=min(grid[i][j],left);\n            }\n            \n        \n            for(int k=n-1,right=0;k>=0;k--){\n                if(grid[i][k]==0)right=0;\n                else right+=1;\n                grid[i][k]=min(grid[i][k],right);\n            }\n            \n            \n            for(int j=0,top=0;j<n;j++){\n                if(grid[j][i]==0)top=0;\n                else top+=1;\n                grid[j][i]=min(grid[j][i],top);\n            }\n             \n            for(int k=n-1,bottom=0;k>=0;k--){\n                if(grid[k][i]==0)bottom=0;\n                else bottom+=1;\n                grid[k][i]=min(grid[k][i],bottom);\n            }\n            \n            }\n            \n            int mxorder=0;\n            for(int i=0;i<n;i++){\n                for(int j=0;j<n;j++){\n                    mxorder=max(mxorder,grid[i][j]);\n                }\n            }\n        \n        return mxorder;\n        }\n    };\n```\n\n\n**C++ DP Shortened Version**\n```\nint orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {\n    vector<vector<int>> grid(n, vector<int>(n, n));\n        \n    for (auto& m : mines) {\n        grid[m[0]][m[1]] = 0;\n    }\n        \n    for (int i = 0; i < n; i++) {\n        for (int j = 0, k = n - 1, left = 0, right= 0, top = 0, bottom = 0; j < n; j++, k--) {\n            grid[i][j] = min(grid[i][j], left = (grid[i][j] == 0 ? 0 : left + 1));\n            grid[i][k] = min(grid[i][k], right = (grid[i][k] == 0 ? 0 : right + 1));\n            grid[j][i] = min(grid[j][i], top = (grid[j][i] == 0 ? 0 : top + 1));\n            grid[k][i] = min(grid[k][i], bottom = (grid[k][i] == 0 ? 0 : bottom + 1));\n        }\n    }\n        \n    int mxorder = 0;\n        \n    for (int i = 0; i < n; i++) {\n        for (int j = 0; j < n; j++) {\n            mxorder = max(mxorder, grid[i][j]);\n        }\n    }\n        \n    return mxorder;\n}\n```\n\n**C++ DFS Version (TLE on some cases)**\n```\nclass Solution {\npublic:\n    int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {\n        vector<vector<int>> grid(N, vector<int>(N, 1));\n        for(auto &p: mines){\n            grid[p[0]][p[1]] = 0;\n        }\n        \n        auto all_ones = [&](int i, int j, int k){\n            if(i - k < 0 || i + k >= N || j - k < 0 || j + k >= N)\n                return false;\n            return grid[i - k][j] && grid[i + k][j] && grid[i][j - k] && grid[i][j + k];\n        };\n        int K = 0;\n        for(int i = 0; i < N; ++i){\n            for(int j = 0; j < N; ++j){\n                if(grid[i][j] == 1){\n                    int k = 1;\n                    while(all_ones(i, j, k))\n                        ++k;\n                    K = max(k, K);\n                }\n            }\n        }\n        return K;\n    }\n};\n```
[]