MCC 2025 P1: Building Fences

Building Fences

Statement

There is a grassy field with fences, which is represented by a grid of $N$ rows and $M$ columns. Each cell consists of grass (.) or a fence (#).

You would like to build a complete vertical wall: a single column of cells that only consists of fences. You can pick any number of grass cells (including zero) and build a fence on each of them, turning them into fence cells. What is the minimum number of fences you need to build to create a complete vertical wall?

Input Format

The first line contains two space-separated integers, $N$ and $M$.

The next $N$ lines describe the field. Each line consists of $M$ characters. Each cell is denoted by ‘.’ if it is grass and ‘#’ if it contains a fence.

Output Format

Output the minimum number of fences you need to build to create a complete vertical wall.

Constraints

For all tasks:

• $1 \le N, M \le 800$.

• The input grid only consists of ‘.’ and ‘#’.

• Task 1 (10 points): $N, M \le 6$
• Task 2 (10 points): $N, M \le 6$
• Task 3 (10 points): $N, M \le 20$
• Task 4 (10 points): $N, M \le 20$
• Task 5 (10 points): $N, M \le 150$
• Task 6 (10 points): $N, M \le 200$
• Task 7 (10 points): $N, M \le 500$
• Task 8 (10 points): $N, M \le 500$
• Task 9 (10 points): $N, M \le 500$
• Task 10 (10 points): $N, M \le 800$

Sample Input

4 5
.....
...#.
.##..
...#.

Sample Output

2

Explanation

The grid has 4 rows and 5 columns. We need to find a column that requires the fewest fences to be completely filled with fences.

• Column 1 is ...., which requires 4 fences.
• Column 2 is ..#., which requires 3 fences.
• Column 3 is ..#., which requires 3 fences.
• Column 4 is .#.#, which requires 2 fences.
• Column 5 is ...., which requires 4 fences.

The minimum number of fences required is 2 for the fourth column.

Membina Pagar

Pernyataan

Terdapat sebuah padang berumput dengan pagar, yang diwakili oleh grid berukuran $N$ baris dan $M$ lajur. Setiap petak mengandungi rumput (.) atau pagar (#).

Anda ingin membina tembok menegak yang lengkap iaitu satu lajur yang hanya terdiri daripada pagar. Anda boleh memilih mana-mana bilangan petak rumput (termasuk sifar) dan membina pagar padanya, menukarkannya menjadi petak pagar. Apakah bilangan pagar minimum yang perlu anda bina untuk menghasilkan tembok menegak yang lengkap?

Format Input

Baris pertama mengandungi dua integer yang dipisahkan oleh ruang, iaitu $N$ dan $M$.

$N$ baris yang seterusnya menerangkan grid padang tersebut. Setiap baris mengandungi $M$ aksara. Setiap petak diwakili oleh . jika ia mengandungi rumput, dan # jika ia mengandungi pagar.

Format Output

Keluarkan bilangan pagar minimum yang perlu dibina untuk menghasilkan tembok menegak yang lengkap.

Kekangan

Untuk semua tugasan:

• $1 \le N, M \le 800$.

• Grid input hanya mengandungi aksara . dan #.

• Tugasan 1 (10 markah): $N, M \le 6$
• Tugasan 2 (10 markah): $N, M \le 6$
• Tugasan 3 (10 markah): $N, M \le 20$
• Tugasan 4 (10 markah): $N, M \le 20$
• Tugasan 5 (10 markah): $N, M \le 150$
• Tugasan 6 (10 markah): $N, M \le 200$
• Tugasan 7 (10 markah): $N, M \le 500$
• Tugasan 8 (10 markah): $N, M \le 500$
• Tugasan 9 (10 markah): $N, M \le 500$
• Tugasan 10 (10 markah): $N, M \le 800$

Contoh Input

4 5
.....
...#.
.##..
...#.

Contoh Output

2

Penjelasan

Grid ini mempunyai 4 baris dan 5 lajur. Kita perlu mencari lajur yang memerlukan bilangan pagar paling sedikit untuk dipenuhi sepenuhnya dengan pagar.

• Lajur 1 ialah ...., memerlukan 4 pagar.
• Lajur 2 ialah ..#., memerlukan 3 pagar.
• Lajur 3 ialah ..#., memerlukan 3 pagar.
• Lajur 4 ialah .#.#, memerlukan 2 pagar.
• Lajur 5 ialah ...., memerlukan 4 pagar.

Bilangan pagar minimum yang diperlukan ialah 2, iaitu untuk lajur keempat.

建栅栏

题目描述

有一块由草地与栅栏构成的场地，用一个 $N$ 行 $M$ 列的网格表示。每个格子要么是草地（.），要么是栅栏（#）。

你想建造一面完整的竖直墙：即一列所有格子均为栅栏（#）。你可以将任意数量的草地格子（包括 0 个）改造成栅栏（即把 . 变成 #）。求最少需要修建多少个栅栏，才能得到一面完整的竖直墙？

输入格式

第一行包含两个整数 $N$ 和 $M$。

接下来的 $N$ 行描述场地。每一行有 $M$ 个字符，. 表示该格是草地，则 # 表示该格是栅栏。

输出格式

输出一个整数 - 表示为了得到一个完整的竖直墙所需最少修建栅栏的格子数。

约束

对于每项任务：

• $1 \le N, M \le 800$。

• 输入的网格字符只会是 . 与 #。

• 任务 1（10 分）：$N, M \le 6$
• 任务 2（10 分）：$N, M \le 6$
• 任务 3（10 分）：$N, M \le 20$
• 任务 4（10 分）：$N, M \le 20$
• 任务 5（10 分）：$N, M \le 150$
• 任务 6（10 分）：$N, M \le 200$
• 任务 7（10 分）：$N, M \le 500$
• 任务 8（10 分）：$N, M \le 500$
• 任务 9（10 分）：$N, M \le 500$
• 任务 10（10 分）：$N, M \le 800$

样例输入

4 5
.....
...#.
.##..
...#.

样例输出

2

样例解释

给定的网格共有4行5列。我们需要找出哪一列是需要建造最少的栅栏使得整列均是栅栏。

• 第1列 是 ...., 需要4个栅栏。
• 第2列 是 ..#., 需要3个栅栏。
• 第3列 是 ..#., 需要3个栅栏。
• 第4列 是 .#.#, 需要2个栅栏。
• 第5列 是 ...., 需要4个栅栏。

第四列是需要建造最少栅栏的（2个栅栏）。