Bãi cỏ ngon nhất

Điểm: 0,06 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

USACO US-Open 2008 - Bronze Division

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bessie dự định cả ngày sẽ nhai cỏ xuân và ngắm nhìn cảnh xuân trên cánh đồng của nông dân John, cánh đồng này được chia thành các ô vuông nhỏ với ~R~ ~(1 \le R \le 100)~ hàng và ~C~ ~(1 \le C \le 100)~ cột. Bessie ước gì có thể đếm được số khóm cỏ trên cánh đồng.

Mỗi khóm cỏ trên bản đồ được đánh dấu bằng một ký tự '#' hoặc là ~2~ ký tự '#' nằm kề nhau (2 ô vuông được gọi là kề nhau nếu chúng có chung 1 cạnh). Cho bản đồ của cánh đồng, hãy nói cho Bessie biết có bao nhiêu khóm cỏ trên cánh đồng.

Ví dụ như cánh đồng dưới dây với ~R = 5~ và ~C = 6~:

    .#....
    ..#...
    ..#..#
    ...##.
    .#....

Cánh đồng này có ~5~ khóm cỏ: một khóm ở hàng đầu tiên, một khóm tạo bởi hàng thứ ~2~ và thứ ~3~ ở cột thứ ~2~, một khóm là ~1~ ký tự nằm riêng rẽ ở hàng ~3~, một khóm tạo bởi cột thứ ~4~ và thứ ~5~ ở hàng ~4~, và một khóm cuối cùng ở hàng ~5~.

Input

Dòng ~1~: ~2~ số nguyên cách nhau bởi dấu cách: ~R~ và ~C~
Dòng ~2~ ...~R + 1~: Dòng ~i + 1~ mô tả hàng ~i~ của cánh đồng với ~C~ ký tự, các ký tự là '#' hoặc '. '.

Input đảm bảo mỗi ký tự '#' nằm kề tối đa 2 ký tự '#' khác.

Output

Dòng ~1~: Một số nguyên cho biết số lượng khóm cỏ trên cánh đồng.

Sample Input

5 6
.#....
..#...
..#..#
...##.
.#....

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

-1

vominhmanh10 đã bình luận lúc 24, Tháng 12, 2025, 13:57

lại BFS

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
a = [s for s in sys.stdin.readlines()]
vis = [[False] * m for _ in range(n)]
res = 0
dir = [(0, 1), (1, 0), (-1, 0), (0, -1)]
for i in range(n):
    for j in range(m):
        if not vis[i][j] and a[i][j] == "#":
            res += 1
            q = deque([(i, j)])
            while q:
                di, dj = q.popleft()
                for dx, dy in dir:
                    ni, nj = di + dx, dj + dy
                    if 0 <= ni < n and 0 <= nj < m and not vis[ni][nj] and a[ni][nj] == "#":
                        q.append((ni, nj))
                        vis[ni][nj] = True
print(res)

-12

WeoBuXCS đã bình luận lúc 6, Tháng 12, 2024, 9:03 ← sửa 5 →

Đã xoá

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.