Overview

Count the number of empty seats . in each row and find the row number with the maximum number of empty seats. If there are multiple rows with the same maximum count, choose the topmost row.

Analysis

The number of . contained in the string \(S_i\) is the number of empty seats in that row. The problem can be solved by counting the number of empty seats for all rows and finding the maximum.

Since both \(H\) and \(W\) are at most \(10\), a naive approach that checks all seats is more than fast enough.

Care must be taken in handling rows with the same number of empty seats. When checking rows from top to bottom, updating the answer even when the count is equal to the current maximum will result in choosing a lower row, leading to a wrong answer.

Therefore, update the answer only when the count is strictly greater than the current maximum. This ensures that even if another row with the same number of empty seats appears later, the earlier (higher) row remains as the answer.

For example, if the number of empty seats in each row from top to bottom is \(2, 4, 4\), the answer is updated at row \(2\), but not at row \(3\). Thus, row \(2\) is correctly chosen.

Algorithm

1. Initialize the maximum number of empty seats found so far, best, to \(-1\), and the answer row number, ans, to \(1\).
2. Check the row number \(i\) in order from \(1\) to \(H\):
   • Count the number of . in \(S_i\) and let it be cnt.
   • If cnt > best, update best to cnt and ans to \(i\).
3. Output ans.

At the moment each row is checked, ans represents “the topmost row with the maximum number of empty seats among the rows checked so far.” Therefore, after checking all rows, the desired answer is obtained.

Complexity

• Time Complexity: \(O(HW)\)
  We process a string of length \(W\) for each of the \(H\) rows.
• Space Complexity: \(O(HW)\)
  The provided code reads and stores the entire input. Excluding the storage of the input, the additional space complexity is \(O(1)\).

Implementation Points

• In Python, the number of empty seats can be counted using string.count('.'). Since it inspects the entire string, there is no need to use W directly in the calculation.

• The update condition should be cnt > best. If cnt >= best is used, a lower row will be chosen in case of a tie.

• Since the number of empty seats is at least \(0\), setting best = -1 guarantees that an update will occur on the first row. Even if all rows have \(0\) empty seats, row \(1\) will correctly be the answer.

• Since data[0] and data[1] are \(H\) and \(W\) respectively, the string for the \(i\)-th row is obtained via data[1 + i].

  Source Code

import sys


def main():
    data = sys.stdin.read().split()
    H = int(data[0])
    W = int(data[1])  # W is given but not needed for the computation
    best = -1
    ans = 1
    for i in range(1, H + 1):
        cnt = data[1 + i].count('.')
        if cnt > best:
            best = cnt
            ans = i
    print(ans)


main()

---

This editorial was generated by gpt-6-astra-medium.