最大加号标志 图解题解

什么样的十字才算一个 k 阶加号

给一个 n × n 的方格，除 mines 列出的地雷是 0，其余都是 1。一个 k 阶加号有一个中心格，从中心往上下左右各伸一条长 k-1 的臂，中心和四条臂必须全踩在 1 上，求盘面能摆的最大阶数 k，没有 1 就返回 0。坐标写成（行号,列号），都从 0 数起。题面例子 n=4、地雷 (0,1) 和 (2,3)，答案 2：走一格全是 1，再走就撞雷或出界。

为什么挨个中心去扩加号会白扫太多次

让每个格子轮流当中心、四个方向一格格往外探，n² 个中心每个最坏花 O(n) 探臂，整套就是 O(n³)。慢就慢在探臂：一个中心要确认自己 k 阶，四条臂各查 k-1 个格子，臂最坏伸到 n，相邻中心的臂还大段重叠、被反复重数。

一个格子能撑多大加号，被四条臂里最短的卡死

先别管加号，只问每个格子朝某方向连着能数出几个 1（遇雷或边界就断）。它当中心时，臂长超不过任何一个方向的连续 1 长度——四条臂要同时成立，只要一条方向 1 不够长，加号就伸不出去。四个方向里最短的那条卡住它，一条臂短，加号就缩到那条的长度。

四个方向各扫一遍，为什么能共用同一张表

开一张和盘面同样大的 dp 表（dp 即动态规划：把每格算过的结果存表里、后面直接取用不重算），dp[i][j] 记以 (i,j) 为中心能撑的臂长。陆地格先填 n（臂长上限，后面往下压——每遍都跟表里的值取较小的、把臂长往小里改，叫压），地雷格填 0。分四遍：逐行从左往右数向左、从右往左数向右（从左扫过去，是在数每格往左能连几个 1），逐列从上往下数向上、从下往上数向下；每数出一个方向的长度就和 dp 当前值取 min，遇 1 加一、遇地雷清零，保证数的是不含雷的连续 1。四个方向互相独立，共用一张表、四遍压完剩的就是四方向最小。

拿 4×4 两颗地雷，把四遍扫描亲手压一遍

用题面 n=4、地雷 (0,1) 和 (2,3)，dp 先填陆地 4、地雷 0。第一遍数向左：第 1 行整行 1，压成 1、2、3、4；第 0 行到 (0,1) 撞雷清零，成 1、0、1、2。第二遍从右往左取 min：(1,3) 向左本是 4，可在最右边、向右只有 1，min(4,1)=1 压回。左右叠完，中间两列留 2、贴边成 1。

第三遍数向上取 min：(1,1) 头顶就是地雷、向上只有 1，横向的 2 被压成 1；(1,2) 上方畅通、向上有 2，min(2,2) 保住 2。第四遍数向下取 min：最底一行向下都只有 1、整行压成 1，而 (2,1) 下方还有一格、向下 2 保住 2。四遍压完，全表只剩 (1,2) 和 (2,1) 是 2，取全表最大得 2。

取 min 写成 max，加号为什么会被夸大

四遍每遍走完整张 n×n 的表，时间是它的常数倍 O(n²)；只用一张 dp 表反复取 min，空间 O(n²)。地雷再多也不改复杂度，规模只看 n。取 min 写成 max，等于一条臂够长就行、加号被夸大成最长那条；数连续 1 遇地雷忘清零，跨地雷的两段会被接成一段；陆地格初值填 0 或 1 而非够大的 n，第一遍 min 就把臂长误压低。

Python

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)

C++

#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;
    }
};

Java

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();
    }
}