Solution

For each row, count the number of . (empty seats), and output the index of the row where this count is maximum.

Scan the rows from top to bottom as i = 1, 2, ..., H, and let cnt be the number of . characters in \(S_i\). Update the running maximum best and the answer ans only when cnt is strictly greater than best.

Proof of correctness

Loop invariant: after processing row i, ans is the topmost row index among rows \(1\) through \(i\) that attains the maximum empty-seat count, and best is that maximum count.

• Initialization (\(i = 0\), nothing processed yet): best = -1. Since every row has a non-negative count, the first row always triggers an update and sets ans = 1.
• Maintenance: if cnt > best, then row i is the unique (hence topmost) maximizer among rows \(1..i\), so we set ans = i. If cnt < best, row i is not a maximizer, so we do not update. If cnt == best, row i is also a maximizer, but ans already points to a higher row with the same count, so we keep ans. The invariant is preserved.
• Termination: when the loop ends at \(i = H\), the invariant says ans is the topmost row achieving the maximum count over all rows — exactly the required answer.

The tie-break is handled naturally by updating only on a strict increase, which selects the topmost row.

Complexity

• Time: \(O(HW)\), including reading the input.
• Space: \(O(W)\) for C++ and \(O(HW)\) for Python, including stored input and output arrays or strings.