最大加号标志 图解题解

这道题到底在问什么

输入

n = 5, mines = [[4,2]]

输出

2

输入

n = 4, mines = [[0,1],[2,3]]

输出

2

最优解：一步一步想明白

1. 3记住这句口诀:加号的臂长被最短的那条方向卡住,所以是四个方向连续 1 的长度取最小值。下面每一帧都在套它。
2. 4绿色 1 = 可用格;红色 0 = 地雷这就是 4 × 4 的盘面。红色的 0 是地雷,在 (0,1) 和 (2,3);其余绿色的格子都是 1。加号的每一格都必须落在绿色的 1 上。
3. 5紫色 = 中心;橙色 = 四个方向各延伸一格先用 (2,1) 试手。把中心点紫,再往上下左右各探一格:上是 (1,1)、下是 (3,1)、左是 (2,0)、右是 (2,2),四个邻居都是 1。四个方向都能走出 1 格,所以这里能撑起 2 阶加号。
4. 6另开一张同样大小的 dp 表,每格记「以它为中心的臂长」。臂长再长也超不过 n,所以陆地格先填 4 这个上限,两颗地雷格直接填 0。接下来四遍扫描会把这些 4 一点点压小。
5. 7第一遍,逐行从左往右扫,数每个格子向左方向(含自己)连续有几个 1。遇到 1 就加一,遇到地雷就清零重来。先拿第 1 行找感觉。
6. 8第 1 行整行都是 1,没有地雷打断,所以向左长度一路累加成 1、2、3、4。这一行越往右,左臂越长。
7. 9再看第 0 行。(0,0) 是 1,记 1;到 (0,1) 撞上地雷,长度清零记 0;过了雷,(0,2) 重新从 1 开始,(0,3) 接着是 2。地雷会把连续段切断,这点很关键。
8. 10四行都这么扫完,整张 dp 表现在装的是每个格子的向左臂长。注意这只是四个方向里的一个,接下来三遍会用更短的方向把它继续压小。
9. 11第二遍反过来,逐行从右往左数向右臂长,数出来后和表里的值取最小。盯住 (1,3):它向左臂长是 4,可它在最右边,向右一步都迈不出去。
10. 12果然,(1,3) 向右只有 1,min(4, 1) 等于 1,它被压回 1。最左边的 (1,0) 正相反,向左只有 1。取 min 的意义就在这:一个方向再长,只要另一个方向短,加号就撑不大。
11. 13两遍叠完,每格装的是左右两个方向的较小值,也就是这一行里横着能伸多远。靠中间的格子(像第 1、2 列)还保留着 2,边上的都被压成了 1。
12. 14第三遍换方向,逐列从上往下数向上臂长,继续取 min。看第 1 列:顶上 (0,1) 是地雷,所以 (1,1) 向上只有 1,(2,1) 是 2,(3,1) 是 3。地雷同样会把竖向也切断。
13. 15(1,1) 头顶就是地雷,向上只有 1,横向的 2 被压成了 1。而 (1,2) 上方一路畅通,向上有 2,和横向的 2 取 min 还是 2,稳稳保住。能不能当大加号的中心,这一步开始分化。
14. 16三遍叠完,每格已经是左、右、上三个方向的最小值。只剩最后一个方向,向下。
15. 17最后一遍,逐列从下往上数向下臂长,再取一次 min。最底下那一行 (第 3 行) 每个格子向下都迈不出去,向下臂长全是 1。
16. 18所以第 3 行整行被向下臂长 1 压成了 1,贴着边界的格子当不了大加号的中心。而 (2,1) 下方还有一格,向下臂长是 2,min(2, 2) 保持 2,它扛住了四个方向。
17. 19四个方向都扫完了,这张表就是最终答案表。每格的值,正是以它为中心能撑起的最大加号阶数。能看到只有 (1,2) 和 (2,1) 两个格子是 2,其余都是 1 或 0。
18. 20最后一步,把整张表扫一遍取最大值。最大就是 2,出现在 (1,2) 和 (2,1)。这就是题目要的答案,和开头说的 2 对上了。
19. 21紫色中心 + 橙色四臂,组成 2 阶加号回到盘面,把 (2,1) 这个 2 阶加号画出来:中心加上下左右各一格,五个格子全是 1,稳稳成立。再大一阶就要伸到第二格,可那样会撞到边界或地雷,所以到 2 为止。
20. 22紫色中心;橙色为想伸出的第二格, 已越界或撞雷想把 (2,1) 升到 3 阶吗?那上臂要伸到 (0,1),可那里是地雷;左臂要伸到 (2,-1),已经出了边界。任何一条臂走不通,加号就升不上去,所以 (2,1) 封顶在 2 阶。
21. 23(1,2) 同样能撑起 2 阶(1,2) 也是一样,上下左右各一格都是 1,同样是 2 阶。两个并列第一,答案取它们的阶数 2,具体在哪个中心并不重要。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
from string import *
from operator import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        dp = [[n] * n for _ in range(n)]
        for x, y in mines:
            dp[x][y] = 0
        for i in range(n):
            left = right = up = down = 0
            for j, k in zip(range(n), reversed(range(n))):
                left = left + 1 if dp[i][j] else 0
                right = right + 1 if dp[i][k] else 0
                up = up + 1 if dp[j][i] else 0
                down = down + 1 if dp[k][i] else 0
                dp[i][j] = min(dp[i][j], left)
                dp[i][k] = min(dp[i][k], right)
                dp[j][i] = min(dp[j][i], up)
                dp[k][i] = min(dp[k][i], down)
        return max(max(v) for v in dp)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        vector<vector<int>> dp(n, vector<int>(n, n));
        for (auto& e : mines) dp[e[0]][e[1]] = 0;
        for (int i = 0; i < n; ++i) {
            int left = 0, right = 0, up = 0, down = 0;
            for (int j = 0, k = n - 1; j < n; ++j, --k) {
                left = dp[i][j] ? left + 1 : 0;
                right = dp[i][k] ? right + 1 : 0;
                up = dp[j][i] ? up + 1 : 0;
                down = dp[k][i] ? down + 1 : 0;
                dp[i][j] = min(dp[i][j], left);
                dp[i][k] = min(dp[i][k], right);
                dp[j][i] = min(dp[j][i], up);
                dp[k][i] = min(dp[k][i], down);
            }
        }
        int ans = 0;
        for (auto& e : dp) ans = max(ans, *max_element(e.begin(), e.end()));
        return ans;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int orderOfLargestPlusSign(int n, int[][] mines) {
        int[][] dp = new int[n][n];
        for (int[] e : dp) {
            Arrays.fill(e, n);
        }
        for (int[] e : mines) {
            dp[e[0]][e[1]] = 0;
        }
        for (int i = 0; i < n; ++i) {
            int left = 0, right = 0, up = 0, down = 0;
            for (int j = 0, k = n - 1; j < n; ++j, --k) {
                left = dp[i][j] > 0 ? left + 1 : 0;
                right = dp[i][k] > 0 ? right + 1 : 0;
                up = dp[j][i] > 0 ? up + 1 : 0;
                down = dp[k][i] > 0 ? down + 1 : 0;
                dp[i][j] = Math.min(dp[i][j], left);
                dp[i][k] = Math.min(dp[i][k], right);
                dp[j][i] = Math.min(dp[j][i], up);
                dp[k][i] = Math.min(dp[k][i], down);
            }
        }
        return Arrays.stream(dp).flatMapToInt(Arrays::stream).max().getAsInt();
    }
}

复杂度

面试官可能追问