#1465. B4286 [蓝桥杯青少年组省赛 2022] 农作物

    ID: 1465 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2022广度优先搜索 BFS搜索深度优先搜索 DFS蓝桥杯青少年组连通块普及−

B4286 [蓝桥杯青少年组省赛 2022] 农作物

题目描述

有一块农田被划分为 N×MN \times M 块,农作物和杂草分布生长在农田中,其中农作物使用大写字母 R 表示,杂草使用大写字母 X 表示。请计算出农田中有几块独立的农作物区域(独立的农作物区域指该区域上下左右都被杂草围住,且 N×MN \times M 以外的区域都是杂草)。例如,样例是 N=4N=4,M=4M=4 的农田,这块 4×44 \times 4 的农田中有 33 块独立的农作物区域。

输入格式

输入分为 N+1N+1 行:

  • 第一行为两个正整数 NN 和 MM(1<N<5001 < N < 500,1<M<5001 < M < 500),表示农田的长和宽,数字间用一个空格隔开;
  • 以下 NN 行每行有 MM 个大写字母,表示每格为农作物或杂草。

输出格式

输出一个整数,表示农田中有几块独立的农作物区域。

输入输出样例 #1

输入 #1

4 4
RRRX
RXRX
XXXR
RXXX

输出 #1

3

本题原题在洛谷:https://www.luogu.com.cn/problem/B4286