B: Hokkaido University Hard Note Please note that the question settings are the same as…
- User
B: Hokkaido University Hard
Note
Please note that the question settings are the same as question A, except for the constraints.
story
Homura-chan, who passed Hokkaido University and is excited about the beginning of a new life. But in front of her, a huge campus awaits ...
"Eh ... I'm not in time for the next class ..."
problem
Hokkaido University Sapporo Campus is famous for being unusually large. The Sapporo campus is represented by rectangular squares with H squares vertically and W squares horizontally. We will use (i, j) to represent the cells that are i-mass from the north and j-mass from the west. There are several buildings on campus, with a'B'if there is a building in the location represented by the square (i, j) and a'.' If not, in c_ {i, j}.
Homura, a freshman at Hokkaido University, was surprised at the size of the campus and was worried about moving between buildings. So I was wondering how far the farthest of the two squares with the building were. Here we define the distance between two pairs of squares (i, j), (i', j') as | i-i'| + | j-j'|.
Homura found this problem difficult for him and asked his classmates for help. Please ask for an answer instead of Homura-chan. Input format
H W c_ {11} c_ {12} ... c_ {1W} :: c_ {H1} c_ {H2} ... c_ {HW}
Constraint
- 2 \ leq H, W \ leq 10 ^ 3
- H and W are integers
- c_ {i, j} is either'B'or'.'.
- At least two of c_ {i, j} are'B'.
Output format
Print the integer that represents the answer on one line.
Input example 1
3 3 B.B ..B .BB
Output example 1
Four
- The longest is between the two points (1,1) and (3,3).
Input example 2
4 3 B .. B .. ... ...
Output example 2
1
- Adjacent positions may be the longest.
Input example 3
6 6 ... B .. B.B.B. .B.B.B ... B.B .B..B. ..B ...
Output example 3
7
Example
Input
3 3 B.B ..B .BB
Output
4
Assistant
We need to compute the maximum Manhattan distance between any two buildings in a grid. H,W up to 1000, and number of buildings could be up to H*W (10^6). Naively O(N^2) is too slow.
We need an efficient way: For Manhattan distance |i-i'|+|j-j'|, we can consider transformation: max over all pairs (i,j) and (i',j') of (i+j) - (i'+j')? Actually, Manhattan distance can be expressed as max of four linear forms:
Let d = |i-i'| + |j-j'| = max( (i+j) - (i'+j'), (i - j) - (i' - j'), (-i+j) - (-i'+j'), (-i - j) - (-i' - j') )? Wait typical trick: For any two points, the Manhattan distance equals max over four combinations of (i * s1 + j * s2) differences with signs. More precisely, we can define four transformed coordinates:
p1 = i + j p2 = i - j p3 = -i + j p4 = -i - j
Then distance = max(p1 - p1', p2 - p2', p3 - p3', p4 - p4')? Actually not exactly. For Manhattan, we have |i-i'|+|j-j'| = max( (i+j) - (i'+j'), (i - j) - (i' - j'), (-i + j) - (-i' + j'), (-i - j) - (-i' - j') ). Because: (i+j) - (i'+j') = (i-i')+(j-j') (i - j) - (i' - j') = (i-i') - (j-j') (-i + j) - (-i' + j') = -(i-i')+(j-j') (-i - j) - (-i' - j') = -(i-i')-(j-j')
The maximum of these four differences equals the maximum of these linear combinations. But the Manhattan distance is actually the maximum of these differences, but only if we also consider that the points could be reversed. Actually, for any two points, the Manhattan distance equals the maximum of (p1 - p1'), (p2 - p2'), (p3 - p3'), (p4 - p4')? Let's test: Suppose i=0,j=0, i'=1,j'=2 => distance = 3. Compute: p1=0, p1'=3 => p1 - p1' = -3. p2=0, p2'=-1 => p2 - p2' = 1. p3=0, p3'=1? Actually -i+j = 0, -i'+j' = -1+2=1 => p3-p3' = -1. p4=0, p4' = -1-2=-3 => p4 - p4' = 3. Max of -3,1,-1,3 = 3, which matches. If we swap the points, the maximum could be negative? But we need max over both orders? Actually, if we consider max over (p for point1 - p for point2) across all points, the maximum over all pairs of (p_k(i,j) - p_k(i',j')) will yield the maximum difference for that linear functional. But the Manhattan distance is max_k |p_k(i,j) - p_k(i',j')|? Not exactly: Note p2 = i - j, the range of difference can be negative. But the absolute difference of i-j is not equal to the Manhattan distance; but the maximum of these four differences (taking both orders) gives the Manhattan distance. More precisely, for Manhattan distance d, we have: d = max( (i+j) - (i'+j'), (i'+j') - (i+j), (i-j) - (i'-j'), (i'-j') - (i-j) )? Actually no: That would be max of absolute differences? Let's derive:
We know that Manhattan distance = max over linear forms: f1 = i+j, f2 = i - j, f3 = -i + j, f4 = -i - j, of |f(i,j) - f(i',j')|? But is it true that d = max(|f1-f1'|, |f2-f2'|, |f3-f3'|, |f4-f4'|)? Check: For (0,0) and (1,2): f1 diff = 3, f2 diff = -1? absolute =1, f3 diff = -1? absolute=1, f4 diff = -3 absolute=3 => max=3, OK. For (1,0) and (0,2): d = |1-0|+|0-2| =1+2=3. f1: 1 vs 2 => diff=1; f2:1-0=1 vs 0-2=-2 => diff=3? Actually f2: i-j =1, for (0,2): 0-2=-2 => |1 - (-2)|=3; So max=3. Indeed, it works: Manhattan distance = max_k |f_k(i,j) - f_k(i',j')| where f_k are these four linear forms. Because Manhattan distance is the L1 norm, and the unit ball in L1 is the convex hull of these four direction vectors, and the dual norm of L1 is Linf, but here we are computing L1 distance via max of absolute differences of these four linear transforms. Actually it's a known trick: For any two points, the Manhattan distance = max( |(i+j)-(i'+j')|, |(i-j)-(i'-j')| ). Wait only two? Because (i+j) and (i-j) suffice? Let's check: For (0,0) and (1,2): |(i+j)-(i'+j')| = 3, |(i-j)-(i'-j')| = |0 - (-1)|? Actually (i-j)=0, (i'-j')=-1 => |0-(-1)|=1, max=3. For (1,0) and (0,2): |(1+0)-(0+2)| = |1-2|=1, |(1-0)-(0-2)| = |1 - (-2)|=3 => max=3. So indeed Manhattan distance = max(|(i+j)-(i'+j')|, |(i-j)-(i'-j')|). Because |i-i'|+|j-j'| = max( (i+j)-(i'+j'), (i'+j')-(i+j), (i-j)-(i'-j'), (i'-j')-(i-j) )? Actually the max of these four values is the same as max( |(i+j)-(i'+j')|, |(i-j)-(i'-j')| ). Because the four values are exactly the two differences and their negatives. So yes, we only need two transforms: s = i+j, d = i-j. Then Manhattan distance = max(|s1-s2|, |d1-d2|)? Wait is that always true? Let's test with (0,0) and (2,2): s diff=4, d diff=0 => max=4, actual Manhattan distance = 4, correct. (0,2) and (2,0): s diff=0, d diff=4 => max=4, actual = 4. (0,0) and (1,1): s diff=2, d diff=0 => max=2, actual = 2. (1,0) and (0,1): s diff=0, d diff=2 => max=2, actual=2. So it seems correct. Actually it's a known result: L1 distance = L∞ distance after transforming by (i+j, i-j) (a 45-degree rotation and scaling). Because mapping (i,j) -> (i+j, i-j) yields coordinates where Manhattan distance becomes Chebyshev distance (max of absolute differences). Indeed, the transformation: let u = i+j, v = i-j. Then |i-i'|+|j-j'| = max(|u-u'|, |v-v'|). Check: |i-i'|+|j-j'| = max( |(u-u')+(v-v')|/2 + |(u-u')-(v-v')|/2? That seems messy. But let's derive: i = (u+v)/2, j = (u-v)/2. Then |i-i'|+|j-j'| = |(Δu+Δv)/2| + |(Δu-Δv)/2| = (|Δu+Δv|+|Δu-Δv|)/2 = max(|Δu|, |Δv|). Because for any real numbers a,b, (|a+b|+|a-b|)/2 = max(|a|,|b|). This is a known identity. So indeed Manhattan distance = max(|Δu|,|Δv|). So we can compute u and v for each building, then we need the maximum Chebyshev distance between any two points in this transformed space, which is simply the maximum of (max u - min u) and (max v - min v). Because the maximum Chebyshev distance between a set of points is the maximum of the ranges in each coordinate: max over pairs of max(|u_i - u_j|, |v_i - v_j|) = max( max_u - min_u, max_v - min_v ). Indeed, the Chebyshev distance between any two points is at most max(range_u, range_v). And there exist points achieving that: the point with max_u and min_u, or max_v and min_v, etc. Actually we need to check if the maximum Chebyshev distance is exactly max(range_u, range_v). For Chebyshev, the farthest points in terms of Chebyshev distance are those that achieve the maximum spread in either coordinate. Formally, for any two points, max(|Δu|,|Δv|) ≤ max(range_u, range_v) because |Δu| ≤ range_u, |Δv| ≤ range_v. And there exists a pair that achieves range_u (by taking min_u and max_u) and then Chebyshev distance = max(range_u, |v difference|) which is at least range_u, but could be > range_u? Actually if we take min_u and max_u, their v difference may be arbitrary, and the Chebyshev distance will be max(range_u, |Δv|). That could be larger than range_u if |Δv| > range_u. But then that |Δv| would be ≤ range_v, so the max would be at most max(range_u, range_v). So the pair (min_u, max_u) yields Chebyshev distance = max(range_u, |Δv|). That might be less than max(range_u, range_v) if |Δv| is small, but there might be another pair that achieves exactly max(range_u, range_v). Typically, the maximum Chebyshev distance among a set equals the maximum of the ranges in each coordinate. Because consider: If range_u >= range_v, then pick points achieving min_u and max_u; their Chebyshev distance = max(range_u, |Δv|). Since |Δv| ≤ range_v ≤ range_u, the max is range_u. So distance = range_u. If range_v > range_u, similarly pick points achieving min_v and max_v, Chebyshev distance = range_v. So maximum Chebyshev distance = max(range_u, range_v). Thus the answer is max( (max_i+j - min_i+j), (max_i-j - min_i-j) ).
But careful: The transformation yields integer values? i+j and i-j are integers. The ranges are integers. That gives the answer.
We need to compute for all cells with B, the min and max of i+j, and min and max of i-j. Then answer = max( (max_sum - min_sum), (max_diff - min_diff) ).
Constraints up to 1000, we can simply scan all cells and update min/max.
Thus O(HW) which is up to 1e6, fine.
Let's test on examples:
Example1: 3x3 B.B ..B .BB List B positions: (1,1) -> sum=2, diff=0; (1,3) sum=4 diff=-2? Actually i=1,j=3 -> sum=4, diff=-2; (2,3) sum=5 diff=-1; (3,2) sum=5 diff=1; (3,3) sum=6 diff=0. Compute min_sum=2, max_sum=6 -> range_sum=4. min_diff = min(0,-2,-1,1,0) = -2, max_diff = max(0,-2,-1,1,0)=1 -> range_diff = 3. Max(4,3)=4. Correct.
Example2: 4 3 B.. B.. ... ... Positions: (1,1): sum=2 diff=0; (2,1): sum=3 diff=1? i=2,j=1: sum=3, diff=1. min_sum=2, max_sum=3 -> range_sum=1. min_diff=0, max_diff=1 -> range_diff=1 -> answer=1. Correct.
Example3: 6 6 ...B.. B.B.B. .B.B.B ...B.B .B..B. ..B... We'll compute maybe but expected answer 7. Should match.
Thus solution straightforward.
Implementation: read H,W, then loop i=1..H, read row string, loop j=1..W, if char == 'B', compute s=i+j, d=i-j, update mins and maxes. Finally answer = max(max_s - min_s, max_d - min_d). Print answer.
Note that i and j are 1-indexed as per problem: i from north, j from west, starting at 1.
Edge case: Only two B's? Works.
Time O(HW) memory O(1).
We'll produce Python code.
But careful: H,W up to 1000, reading input with sys.stdin.
We'll set initial min_sum = large (like INF) and max_sum = -INF. Similarly for diff.
Alternatively, we could store all positions and compute but not necessary.
Implementation:
def solve(): import sys input = sys.stdin.readline H,W = map(int, input().split()) INF = 10**9 min_sum = INF max_sum = -INF min_diff = INF max_diff = -INF for i in range(1, H+1): row = input().strip() # maybe row length could be without spaces? It's given as continuous characters without spaces. The input format: "c_{11} c_{12} ... c_{1W}" but actually they are likely written without spaces? The examples show: "B.B" as a string. So it's a string of length W, no spaces. So row = line.strip(). for j,ch in enumerate(row, start=1): if ch == 'B': s = i+j d = i-j if s < min_sum: min_sum = s if s > max_sum: max_sum = s if d < min_diff: min_diff = d if d > max_diff: max_diff = d ans = max(max_sum - min_sum, max_diff - min_diff) print(ans)
This should work.
But note: In the problem statement, the input lines might have spaces? It says "c_{11} c_{12} ... c_{1W}". Usually in programming contest, they'd write without spaces? Actually the format shows as "c_ {11} c_ {12} ... c_ {1W}" which suggests that each character is separated by spaces? But in examples, they show "B.B" as a continuous string. It's ambiguous. Usually in AtCoder (this appears like AtCoder problem "Hokkaido University Hard"?), they'd input as a string without spaces. However the input format description: "c_ {11} c_ {12} ... c_ {1W}" might be a formatting artifact. The examples: 3 3 then B.B, which is a string without spaces. So we treat as a string.
We can use .split() or direct string? If there were spaces, the row would contain characters separated by spaces; but then row length would be more than W. Since we know each row has exactly W characters, we can read the line and filter out spaces if any. Safer: read the line, if it contains spaces, split and then combine? But it's easier to just read line and replace spaces: row = input().strip().replace(' ', '') . That works for both.
Let's adjust: row = input().strip().replace(' ', ''). Then ensure length is W.
Alternatively, use row = ''.join(input().split()).
We'll implement: row = ''.join(input().split()) to remove any spaces.
Ok.
Now final answer.
But there is nuance: The answer is integer. Print it.
Thus solution done.
I'll now produce final answer. ```python
import sys
def solve() -> None: input = sys.stdin.readline H, W = map(int, input().split())
INF = 10**9 min_sum = INF max_sum = -INF min_diff = INF max_diff = -INF for i in range(1, H + 1): # read row, removing possible spaces row = ''.join(input().split()) for j, ch in enumerate(row, start=1): if ch == 'B': s = i + j d = i - j if s < min_sum: min_sum = s if s > max_sum: max_sum = s if d < min_diff: min_diff = d if d > max_diff: max_diff = d ans = max(max_sum - min_sum, max_diff - min_diff) print(ans)if name == "main": solve()