Croatian Olympiad in Informatics
April \(28^{st}\) 2024
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 t\(op-le\)ft and bott\(om-ri\)ght fields will definitely contain cheese.
Let’s denote the number of minions as \(K\). Your minions will start their exploration in the t\(op-le\)ft field
and finish in the bott\(om-ri\)ght 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 pat\(hs - th\)ey intersect
(b) Invalid choice of pat\(hs - th\)ey approach a hole from
the same side

In all subtasks, \(2 \le N\), \(M \le 2000\).
Subtask
Score
Constraints
1
15
All holes are in the same row.
2
18
N, \(M \le 10\)
3
16
N, \(M \le 50\), there are no holes in the first or last row or in the first or last column.
4
18
N, \(M \le 50\)
5
16
N, \(M \le 2000\), there are no holes in the first or last row or in the first or last column.
6
17
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.
Croatian Olympiad in Informatics
April \(28^{st}\) 2024

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

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

출처 COCI 2023/2024 Olympiad