Falling Sand (Easy Version)

题意翻译

这是本题的**简单版本**。简单版本与困难版本的区别在于 $a_i$ 的数据范围。 给你一个 $n$ 行 $m$ 列的网格和一个长度为 $m$ 的序列 $a$。每个位置要么是空的，要么有一块沙子。**本题中，我们保证 $a_i$ 的值等于网格第 $i$ 列的沙子块数。** 你可以选择任意一块仍然在网格中的沙子并“干扰”这块沙子。当一块沙子被“干扰”后，它会从当前位置竖直下落，并最终掉出网格。另外，所有与一块下落的沙子经过的任意位置相邻的沙子也会开始竖直下落，**任意下落的沙子都会使相邻的沙子下落**（如果这一段看不懂，可以阅读样例，样例中用黑色方框标记的是被“干扰”的沙子，用叉标记的是自动下落的沙子）。 你的目标是使第 $i$ 列有 $a_i$ 块沙子掉出网格（根据 $a_i$ 的数据范围，你需要使网格中的所有沙子都掉出网格）。 求你最少需要“干扰”多少块沙子。 $1\leq n\times m\leq4\times10^5$，$0\leq a_i\leq n$。 网格由字符 `.` 和字符 `#` 构成，`.` 表示这个位置是空的，`#` 表示这个位置有一块沙子。 $a_i$ 等于网格第 $i$ 列的沙子块数。

题目描述

This is the easy version of the problem. The difference between the versions is the constraints on $ a_i $ . You can make hacks only if all versions of the problem are solved. Little Dormi has recently received a puzzle from his friend and needs your help to solve it. The puzzle consists of an upright board with $ n $ rows and $ m $ columns of cells, some empty and some filled with blocks of sand, and $ m $ non-negative integers $ a_1,a_2,\ldots,a_m $ ( $ 0 \leq a_i \leq n $ ). In this version of the problem, $ a_i $ will be equal to the number of blocks of sand in column $ i $ . When a cell filled with a block of sand is disturbed, the block of sand will fall from its cell to the sand counter at the bottom of the column (each column has a sand counter). While a block of sand is falling, other blocks of sand that are adjacent at any point to the falling block of sand will also be disturbed and start to fall. Specifically, a block of sand disturbed at a cell $ (i,j) $ will pass through all cells below and including the cell $ (i,j) $ within the column, disturbing all adjacent cells along the way. Here, the cells adjacent to a cell $ (i,j) $ are defined as $ (i-1,j) $ , $ (i,j-1) $ , $ (i+1,j) $ , and $ (i,j+1) $ (if they are within the grid). Note that the newly falling blocks can disturb other blocks. In one operation you are able to disturb any piece of sand. The puzzle is solved when there are at least $ a_i $ blocks of sand counted in the $ i $ -th sand counter for each column from $ 1 $ to $ m $ . You are now tasked with finding the minimum amount of operations in order to solve the puzzle. Note that Little Dormi will never give you a puzzle that is impossible to solve.

输入输出格式

输入格式

The first line consists of two space-separated positive integers $ n $ and $ m $ ( $ 1 \leq n \cdot m \leq 400\,000 $ ). Each of the next $ n $ lines contains $ m $ characters, describing each row of the board. If a character on a line is '.', the corresponding cell is empty. If it is '\#', the cell contains a block of sand. The final line contains $ m $ non-negative integers $ a_1,a_2,\ldots,a_m $ ( $ 0 \leq a_i \leq n $ ) — the minimum amount of blocks of sand that needs to fall below the board in each column. In this version of the problem, $ a_i $ will be equal to the number of blocks of sand in column $ i $ .

输出格式

Print one non-negative integer, the minimum amount of operations needed to solve the puzzle.

输入输出样例

输入样例 #1

5 7
#....#.
.#.#...
#....#.
#....##
#.#....
4 1 1 1 0 3 1

输出样例 #1

3

输入样例 #2

3 3
#.#
#..
##.
3 1 1

输出样例 #2

1

说明

For example $ 1 $ , by disturbing both blocks of sand on the first row from the top at the first and sixth columns from the left, and the block of sand on the second row from the top and the fourth column from the left, it is possible to have all the required amounts of sand fall in each column. It can be proved that this is not possible with fewer than $ 3 $ operations, and as such the answer is $ 3 $ . Here is the puzzle from the first example. For example $ 2 $ , by disturbing the cell on the top row and rightmost column, one can cause all of the blocks of sand in the board to fall into the counters at the bottom. Thus, the answer is $ 1 $ . Here is the puzzle from the second example.