文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

在一個大小在 (0, 0) 到 (N-1, N-1) 的2D網格 grid 中，除了在 mines 中給出的單元為 0，其他每個單元都是 1。網格中包含 1 的最大的軸對齊加號標志是多少階？返回加號標志的階數。如果未找到加號標志，則返回 0。

一個 k" 階由 1 組成的“軸對稱”加號標志具有中心網格 grid[x][y] = 1 ，以及4個從中心向上、向下、向左、向右延伸，長度為 k-1，由 1 組成的臂。

下面給出 k" 階“軸對稱”加號標志的示例。
注意，只有加號標志的所有網格要求為 1，別的網格可能為 0 也可能為 1。

示例 1： 輸入: N = 5, mines = [[4, 2]] 輸出: 2 在上面的網格中，最大加號標志的階只能是2。一個標志已在圖中標出。

示例 2： 輸入: N = 2, mines = [] 輸出: 1 解釋: 11 11 沒有 2 階加號標志，有 1 階加號標志。示例 3： 輸入: N = 1, mines = [[0, 0]] 輸出: 0 解釋: 0 沒有加號標志，返回 0 。提示： 整數N 的范圍： [1, 500]. mines 的最大長度為 5000. mines[i] 是長度為2的由2個 [0, N-1] 中的數組成. (另外,使用 C, C++, 或者 C# 編程將以稍小的時間限制進行??判斷.)

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/largest-plus-sign
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 動態規劃，記錄每個位置上4個方向上的連續 1 的個數，時間復雜度 $O(N^2)$

class Solution { public:int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {vector<vector<int>> g(N, vector<int>(N, 1));for(auto& m : mines)g[m[0]][m[1]] = 0;vector<vector<int>> up(N, vector<int>(N, 0));//該方向上的連續1的個數vector<vector<int>> left(N, vector<int>(N, 0));vector<vector<int>> down(N, vector<int>(N, 0));vector<vector<int>> right(N, vector<int>(N, 0));for(int i = 0; i < N; i++){for(int j = 0; j < N; j++){if(g[i][j] == 0)continue;left[i][j] = (j > 0 ? left[i][j-1] : 0) + 1;up[i][j] = (i > 0 ? up[i-1][j] : 0) + 1;}}for(int i = N-1; i >= 0; i--){for(int j = N-1; j >= 0; j--){if(g[i][j] == 0)continue;right[i][j] = (j < N-1 ? right[i][j+1] : 0) + 1;down[i][j] = (i < N-1 ? down[i+1][j] : 0) + 1;}}int ans = 0;for(int i = 0; i < N; i++){for(int j = 0; j < N; j++)ans = max(ans, min(left[i][j], min(right[i][j],min(up[i][j], down[i][j]))));}return ans;} };

352 ms 87.7 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 764. 最大加号标志（DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。