Lena and Matrix (Codeforces 1689D)
Tags: Others, geometry

Lena is a beautiful girl who likes logical puzzles.As a gift for her birthday, Lena got a matrix puzzle!The matrix consists of $$$n$$$ rows and $$$m$$$ columns, and each cell is either black or white. The coordinates $$$(i,j)$$$ denote the cell which belongs to the $$$i$$$-th row and $$$j$$$-th column for every $$$1\leq i \leq n$$$ and $$$1\leq j \leq m$$$. To solve the puzzle, Lena has to choose a cell that minimizes the Manhattan distance to the farthest black cell from the chosen cell.More formally, let there be $$$k \ge 1$$$ black cells in the matrix with coordinates $$$(x_i,y_i)$$$ for every $$$1\leq i \leq k$$$. Lena should choose a cell $$$(a,b)$$$ that minimizes $$$$$$\max_{i=1}^{k}(|a-x_i|+|b-y_i|).$$$$$$As Lena has no skill, she asked you for help. Will you tell her the optimal cell to choose? 

Input: There are several test cases in the input data. The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 10\,000$$$) — the number of test cases. This is followed by the test cases description.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2\leq n,m \leq 1000$$$)  — the dimensions of the matrix. The following $$$n$$$ lines contain $$$m$$$ characters each, each character is either 'W' or 'B'. The $$$j$$$-th character in the $$$i$$$-th of these lines is 'W' if the cell $$$(i,j)$$$ is white, and 'B' if the cell $$$(i,j)$$$ is black. It is guaranteed that at least one black cell exists.It is guaranteed that the sum of $$$n\cdot m$$$ does not exceed $$$10^6$$$.

Output: For each test case, output the optimal cell $$$(a,b)$$$ to choose. If multiple answers exist, output any.

Note: In the first test case the two black cells have coordinates $$$(1,1)$$$ and $$$(3,2)$$$. The four optimal cells are $$$(1,2)$$$, $$$(2,1)$$$, $$$(2,2)$$$ and $$$(3,1)$$$. It can be shown that no other cell minimizes the maximum Manhattan distance to every black cell.In the second test case it is optimal to choose the black cell $$$(2,2)$$$ with maximum Manhattan distance being $$$2$$$.

Sample Inputs:
5
3 2
BW
WW
WB
3 3
WWB
WBW
BWW
2 3
BBB
BBB
5 5
BWBWB
WBWBW
BWBWB
WBWBW
BWBWB
9 9
WWWWWWWWW
WWWWWWWWW
BWWWWWWWW
WWWWWWWWW
WWWWBWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWB

Sample Outputs:
2 1
2 2
1 2
3 3
6 5

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for tc in range(t):
    (n, m) = map(int, input().split())
    mins = 999999
    mind = 999999
    maxs = -999999
    maxd = -999999
    ansi = 0
    ansj = 0
    p = [[999999, 0, 0], [999999, 0, 0], [-999999, 0, 0], [-999999, 0, 0]]
    for i in range(n):
        s = input()
        for j in range(m):
            if s[j] == 'B':
                if i + j < p[0][0]:
                    p[0][0] = i + j
                    p[0][1] = i
                    p[0][2] = j
                if i - j < p[1][0]:
                    p[1][0] = i - j
                    p[1][1] = i
                    p[1][2] = j
                if i + j > p[2][0]:
                    p[2][0] = i + j
                    p[2][1] = i
                    p[2][2] = j
                if i - j > p[3][0]:
                    p[3][0] = i - j
                    p[3][1] = i
                    p[3][2] = j
    mincost = 999999
    mid1 = (p[0][0] + p[2][0]) // 2
    mid2 = (p[1][0] + p[3][0]) // 2
    midi = (mid1 + mid2) // 2
    midj = (mid1 - mid2) // 2
    for i in range(midi, midi + 2):
        for j in range(midj, midj + 2):
            cost = max(abs(i - p[0][1]) + abs(j - p[0][2]), abs(i - p[1][1]) + abs(j - p[1][2]), abs(i - p[2][1]) + abs(j - p[2][2]), abs(i - p[3][1]) + abs(j - p[3][2]))
            if cost < mincost:
                mincost = cost
                ansi = i
                ansj = j
    print(ansi + 1, ansj + 1)

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for tc in range(t):
    (n, m) = map(int, input().split())
    (mins, mind, maxs, maxd, ansi, ansj) = (999999, 999999, -999999, -999999, 0, 0)
    p = [[999999, 0, 0], [999999, 0, 0], [-999999, 0, 0], [-999999, 0, 0]]
    for i in range(n):
        s = input()
        for j in range(m):
            if s[j] == 'B':
                if i + j < p[0][0]:
                    (p[0][0], p[0][1], p[0][2]) = (i + j, i, j)
                if i - j < p[1][0]:
                    (p[1][0], p[1][1], p[1][2]) = (i - j, i, j)
                if i + j > p[2][0]:
                    p[2][0] = i + j
                    p[2][1] = i
                    p[2][2] = j
                if i - j > p[3][0]:
                    (p[3][0], p[3][1], p[3][2]) = (i - j, i, j)
    mincost = 999999
    mid1 = (p[0][0] + p[2][0]) // 2
    mid2 = (p[1][0] + p[3][0]) // 2
    midi = (mid1 + mid2) // 2
    midj = (mid1 - mid2) // 2
    for i in range(midi - 1, midi + 2):
        for j in range(midj - 1, midj + 2):
            cost = max(abs(i - p[0][1]) + abs(j - p[0][2]), abs(i - p[1][1]) + abs(j - p[1][2]), abs(i - p[2][1]) + abs(j - p[2][2]), abs(i - p[3][1]) + abs(j - p[3][2]))
            if cost < mincost:
                (mincost, ansi, ansj) = (cost, i, j)
    print(ansi + 1, ansj + 1)

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    (n, m) = map(int, input().split())
    p = [[999999, 0, 0], [999999, 0, 0], [-999999, 0, 0], [-999999, 0, 0]]
    for i in range(n):
        s = input()
        for j in range(m):
            if s[j] == 'B':
                if i + j < p[0][0]:
                    p[0][0] = i + j
                    p[0][1] = i
                    p[0][2] = j
                if i - j < p[1][0]:
                    p[1][0] = i - j
                    p[1][1] = i
                    p[1][2] = j
                if i + j > p[2][0]:
                    p[2][0] = i + j
                    p[2][1] = i
                    p[2][2] = j
                if i - j > p[3][0]:
                    p[3][0] = i - j
                    p[3][1] = i
                    p[3][2] = j
    minCost = 999999
    mid1 = (p[0][0] + p[2][0]) // 2
    mid2 = (p[1][0] + p[3][0]) // 2
    midrow = (mid1 + mid2) // 2
    midcol = (mid1 - mid2) // 2
    for i in range(midrow, midrow + 2):
        for j in range(midcol, midcol + 2):
            cost = max(abs(i - p[0][1]) + abs(j - p[0][2]), abs(i - p[1][1]) + abs(j - p[1][2]), abs(i - p[2][1]) + abs(j - p[2][2]), abs(i - p[3][1]) + abs(j - p[3][2]))
            if cost < minCost:
                minCost = cost
                ansi = i
                ansj = j
    print(ansi + 1, ansj + 1)