Sirologija

You are an ant, but not just any ant – you’re an ant obsessed with cheeseology!
You’ve discovered a new slice of cheese in the kitchen and want to send as many of your minions as
possible to explore it. Imagine the cheese as a table with \(N\) rows and \(M\) columns, where the rows are
labeled from 1 to \(N\) from top to bottom, and the columns are labeled from 1 to \(M\) from left to right.
Some fields contain holes, while others contain cheese. We will denote the field in the \(r\)-th row and \(s\)-th
column as (r, s). The top-left and bottom-right fields will definitely contain cheese.
Let’s denote the number of minions as \(K\). Your minions will start their exploration in the top-left field
and finish in the bottom-right field. They can only move downwards and to the right. Additionally, their
paths must not "cross", meaning we can assign labels from 1 to \(K\) to them in such a way that there is no
field from which a minion with a lower label exited to the right, and a minion with a higher label exited
downwards.
Moreover, you would like these paths to be "different" in some sense, meaning that for every two minions,
there exists a field (r, s) containing a hole, such that one of them was at some point in column \(s\) and in a
row labeled lower than \(r\), while the other was at some point (not necessarily simultaneously) in column \(s\)
and in a row labeled higher than \(r\). Informally, every pair of minions approached some hole from different
sides.
Output the maximum value of \(K\) such that there exists a selection of minion paths satisfying the given
conditions.
Some examples of paths that do not satisfy the conditions:
(a) Invalid choice of paths - they intersect
(b) Invalid choice of paths - they approach a hole from
the same side

Subtask 1 (15 points): All holes are in the same row.

Subtask 2 (18 points): N, \(M \le 10\)

Subtask 3 (16 points): N, \(M \le 50\), there are no holes in the first or last row or in the first or last column.

Subtask 4 (18 points): N, \(M \le 50\)

Subtask 5 (16 points): N, \(M \le 2000\), there are no holes in the first or last row or in the first or last column.

Subtask 6 (17 points): No additional constraints.

The first line contains positive integers \(N\), \(M\).
The next \(N\) lines contain descriptions of the table rows. The \(i\)-th line contains \(M\) characters, where .
denotes cheese and # denotes a field containing a hole.

Output the maximum possible value of the number \(K\) in a single line.

생성자가 기록되지 않았습니다.

출처 COI 2024