---
# System prepended metadata

title: COI 24 Sirologija
tags: [statement]

---

# COI 24 Sirologija 

https://www.acmicpc.net/problem/31984

You are an ant, and not just any ant, but an ant obsessed with cheese!

You have discovered a new slice of cheese in the kitchen, and you want to send as many of your minions as possible to explore the cheese. We can imagine the cheese as a grid with $N$ rows and $M$ columns, where the rows are numbered from $1$ to $N$ from top to bottom, and the columns are numbered from $1$ to $M$ from left to right. Some cells contain holes, while the rest are cheese. The cell in the $r$-th row and $s$-th column will be denoted as $(r, s)$. The top-left cell and the bottom-right cell will surely contain cheese.

Let's denote the number of minions as $K$. Your minions will start their exploration in the top-left cell and finish in the bottom-right cell. They can only move down and right. Additionally, their paths must not "cross"; that is, we can assign them labels from $1$ to $K$ such that there is no cell from which a minion with a smaller label moved right while a minion with a larger label moved down.

Moreover, you want these paths to be "different" in some sense, meaning that for every two minions, there exists a cell $(r, s)$ containing a hole such that one of them was at some point in column $s$ and row with a label smaller than $r$, while the other was at some point (not necessarily the same) in column $s$ and row with a label greater than $r$. Informally, each pair of minions circumnavigated a hole from different sides.

Print the maximum value of $K$ such that there exists a selection of minion paths that satisfy the given conditions.

Some examples of paths that do not satisfy the conditions:

![image](https://hackmd.io/_uploads/BkSrUvCLC.png)
(a) they cross each other
(b) they navigate around the hole from the same side

## Input

In the first line are the natural numbers $N$ and $M$.

In the next $N$ lines are the descriptions of the rows of the grid. In the $i$-th row, there are $M$ characters where . represents cheese and # represents a hole.

## Output

In a single line, output the maximum possible value of the number $K$.

## Constraints and Subtasks

In all subproblems, it holds that $2 \le N, M \le 2000$.

![image](https://hackmd.io/_uploads/BkC2LD0IR.png)

### Sample Input 1

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

### Sample Output 1

`3`

### Sample Input 2

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

### Sample Output 2

`1`

### Sample Input 3

    3 2
    .#
    #.
    ..

### Sample Output 3

`0`
###  Explanation

In the first example, the largest $K$ is $3$. We can send three different groups of ants, each taking a different path that meets the given conditions.

In the second example, the largest $K$ is $1$. The holes in the grid make it impossible for more than one group to meet the conditions.

In the third example, the largest $K$ is $0$. There are too many holes that block all possible paths.

![image](https://hackmd.io/_uploads/Hy0wLDA8C.png)
(a) Example of path choice from the first example
(b) Example of path choice from the second example