Background

Source: https://hsin.hr/hio2024/. The translation comes from Wenxin Yiyan. If you have a better translation, please provide it in the discussion area.

Problem Description

You are an ant, but not an ordinary ant—you are an ant obsessed with the study of cheese. You have discovered a new piece of cheese in the kitchen and want to send as many of your subordinates (little ants) as possible to explore it. Imagine this piece of cheese as a grid with $N$ rows and $M$ columns. Rows are numbered from $1$ to $N$ from top to bottom, and columns are numbered from $1$ to $M$ from left to right. Some cells contain holes, while the others contain cheese. We denote the cell in row $r$ and column $s$ as $(r, s)$. The top-left cell and the bottom-right cell are guaranteed to contain cheese.

Let the number of subordinates be $K$. Your subordinates will start exploring from the top-left cell and finish at the bottom-right cell. They may only move down or right. Also, their paths must not “cross”. This means we can assign them numbers from $1$ to $K$ such that, for any cell, the subordinate with the smaller number is the one that moves right from that cell, while the subordinate with the larger number is the one that moves down from that cell.

In addition, you want these paths to be “different” in a certain sense: for every pair of subordinates, there exists a hole cell $(r, s)$ such that one subordinate is, at some time, in column $s$ at a row index less than $r$, and the other subordinate is, at some (not necessarily the same) time, also in column $s$ but at a row index greater than $r$. Informally, every pair of subordinates approaches a hole from different sides.

Output the maximum value of $K$ for which it is possible to choose paths satisfying the given conditions.

Here are some examples of path sets that do not satisfy the conditions:

Input Format

The first line contains two positive integers $N, M$.

The next $N$ lines describe the grid. The $i$-th line contains $M$ characters, where . means cheese and # means a hole.

Output Format

Output the maximum value of $K$ for which it is possible to choose paths satisfying the given conditions.

5 5
.....
.#...
.....
...#.
.....

3

5 5
....#
....#
.....
.....
#....

1

3 2
.#
#.
..

0

Hint

Constraints

• Subtask 1 (15 points): All holes are in the same row.
• Subtask 2 (18 points): $N, M \leq 10$.
• Subtask 3 (16 points): $N, M \leq 50$, and there are no holes in the first row, last row, first column, and last column.
• Subtask 4 (18 points): $N, M \leq 50$.
• Subtask 5 (16 points): $N, M \leq 2000$, and there are no holes in the first row, last row, first column, and last column.
• Subtask 6 (17 points): No additional constraints.

In all subtasks, $2 \leq N, M \leq 2000$.

Translated by ChatGPT 5