C++ Simple Dynamic-Programming Solution, With Explanation
Idea:\nFirst, we create the matrix of 1\'s and 0\'s.\nThen, we fill the DP matrix the following way:\nWe iterate through the matrix in four ways - left tp right
**Idea:**\nFirst, we create the matrix of 1\'s and 0\'s.\nThen, we fill the DP matrix the following way:\nWe iterate through the matrix in four ways - left tp right, right to left, top to bottom, bottom to top.\nWe fill the maximum length of contiguous 1\'s.\nWe store in the dp matrix the minimum of all directions.\n=> \nAfter `fillDP`, we have a matrix where each position has the largest plus sign centered in that cell.\n```\nclass Solution {\npublic:\n    void fillDP(vector<vector<int>>& dp, vector<vector<int>>& mat, int n) {\n        int down, right, up, left;\n        \n        for (int i = 0; i < n; i++) {\n            down = 0, right = 0;\n            \n            for (int j = 0; j < n; j++) {\n                right = mat[i][j] ? right+1 : 0;\n                dp[i][j] = min(dp[i][j], right);\n                \n                down = mat[j][i] ? down+1 : 0;\n                dp[j][i] = min(dp[j][i], down);\n            }\n        }\n        \n        for (int i = 0; i < n; i++) {\n            up = 0, left = 0;\n            for (int j = n-1; j >= 0; j--) {\n                left = mat[i][j] ? left+1 : 0;\n                dp[i][j] = min(dp[i][j], left);\n                \n                up = mat[j][i] ? up+1 : 0;\n                dp[j][i] = min(dp[j][i], up);\n            }\n        }\n    }\n    \n    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {\n        vector<vector<int>> dp(n, vector<int>(n, INT_MAX));\n        vector<vector<int>> mat(n, vector<int>(n, 1));\n        \n        for (auto mine : mines)\n            mat[mine[0]][mine[1]] = 0;\n        \n        fillDP(dp, mat, n);\n        \n        int res = 0;\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                res = max(res, dp[i][j]);\n            }\n        }\n        return res;\n    }\n};\n```\n**Like it? please upvote!**
['C']