[Solution] Lena and Matrix Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Lena and Matrix Codeforces Solution | Codeforces Problem Solution 2022

D. Lena and Matrix

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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$n$ rows and m$m$ columns, and each cell is either black or white. The coordinates (i,j)$(i,j)$ denote the cell which belongs to the i$i$-th row and j$j$-th column for every 1≤i≤n$1\le i\le n$ and 1≤j≤m$1\le j\le 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≥1$k\ge 1$ black cells in the matrix with coordinates (xi,yi)$(x_i,y_i)$ for every 1≤i≤k$1\le i\le k$. Lena should choose a cell (a,b)$(a,b)$ that minimizes

Solution Click Below:-  CLICK HERE

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$t$ (1≤t≤10000$1\le t\le 10000$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains two integers n$n$ and m$m$ (2≤n,m≤1000$2\le n,m\le 1000$)  — the dimensions of the matrix.

Lena and Matrix Codeforces Solution

Lex String Codeforces Solution

Mystic Permutation Codeforces Solution 

Infected Tree Codeforces Solution

ANDfinity Codeforces Solution

The following n$n$ lines contain m$m$ characters each, each character is either 'W' or 'B'. The j$j$-th character in the i$i$-th of these lines is 'W' if the cell (i,j)$(i,j)$ is white, and 'B' if the cell (i,j)$(i,j)$ is black.

It is guaranteed that at least one black cell exists.

It is guaranteed that the sum of n⋅m$n\cdot m$ does not exceed 106${10}^6$.

Output

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