#P16354. [2026年山东第二轮集训]又见星图

[2026年山东第二轮集训]又见星图

题目描述

一个星座可以看成一个由 n×mn\times m 颗恒星构成的矩形,其中坐标 (i,j)(i,j) 处有一颗亮度为 ai,ja_{i,j} 的恒星。坐标为 (r,c)(r,c) 的恒星是这个星座的中心。

用 di,jd_{i,j} 表示坐标 (i,j)(i,j) 处的恒星到星座中心的曼哈顿距离,即

di,j=∣r−i∣+∣c−j∣.d_{i,j}=|r-i|+|c-j|.

称一个星座构成一个星图,当且仅当距离星座中心越近的恒星亮度越高,即满足:

  • 对于任意两个位置 (i,j)(i,j) 和 (i′,j′)(i',j'),若
di,j≤di′,j′,d_{i,j}\le d_{i',j'},

则有

ai,j≥ai′,j′.a_{i,j}\ge a_{i',j'}.

你可以对这个星座进行若干次修改,使其形成一个星图。每次可以选择下面两种操作之一。

  1. 选择四个整数 i,l,r,vi,l,r,v,然后对于所有 j=l,l+1,…,rj=l,l+1,\ldots,r,令
ai,j=min⁡(ai,j,v).a_{i,j}=\min(a_{i,j},v).
  1. 选择四个整数 i,l,r,vi,l,r,v,然后对于所有 j=l,l+1,…,rj=l,l+1,\ldots,r,令
aj,i=min⁡(aj,i,v).a_{j,i}=\min(a_{j,i},v).

请你求出,最少需要多少次操作,才能将该星座修改成一个星图。

输入格式

第一行包含四个整数 n,m,r,cn,m,r,c。

接下来 nn 行,第 ii 行包含 mm 个整数,依次表示

ai,1,ai,2,…,ai,m.a_{i,1},a_{i,2},\ldots,a_{i,m}.

输出格式

输出一个非负整数,表示最少需要的操作次数。

样例 1

输入

3 3 2 2
1 2 1
1 3 1
2 1 1

输出

2

数据范围与子任务

对于全部数据:

1≤n,m≤160,1\le n,m\le 160, 1≤r≤n,1≤c≤m,1\le r\le n,\qquad 1\le c\le m, 1≤ai,j≤nm.1\le a_{i,j}\le nm.
子任务编号 分值 n≤n\le m≤m\le 特殊性质
1 4 11 160160 无
2 6 44 ai,j≤2a_{i,j}\le 2
3 10 33 2020 无
4 15 5050 r=c=1r=c=1,ai,j≤2a_{i,j}\le 2
5 2525 r=c=1r=c=1
6 无
7 7575
8 20 160160