列表

详情


NC20357. [SDOI2013]城市规划

描述

A 市的市长打算在海边开发一段地带。这个地带看成是一个N×M的方格阵。每个格子可以是建筑、道路或者草地。这片地带是要出租给某些公司,但是这些公司的要求很奇怪。他们要求租给他们的建筑要通过道路形成一个连通块。同一个连通块只能租给一家公司。这 个N×M的方格阵是用字符组成的:O,.,+,|,-,其z中O表示建筑,'.' 表示草地。|,-,+表示道路,分别表示把上下,左右、上下左右的格子连起来。相邻的O表示这是一个建筑物。

由于规划可能不太好,可能某些连通块里面只有道路,这里道路是不能出租的!由于最后这块地的选取可能有部分会与其他市共冋开发,所以最后会在这个NM 中选取一段出来,最后选取出来的是一个Ni×M(0<N1N)的地段。A市的市长想弄要一个规划软件,支持以下功能:

  1. 改变一个格
  2. 询问某块地带有多少个带建筑的连通块。

输入描述

第一行两个整数 N, M ,如题意所示
接下来的 N 行,每行 M 个字符表示这片地带的初始情况。
接下来的一行一个整数Q,表示操作次数
就下来的 Q 行,每行有两种格式:
C i j k : 把第 i 行第 j 个格子修改成
k Q l r: 询问 (l, 1) (r, M) 这块地带连通块个数

输出描述

对于每个询问中的 Q,输出一行,一个数字,表示当前的连通块个数

示例1

输入:

4  4
.O.. 
O+O| 
.O.. ..OO 
4 
Q 1 4 
C 2 4 + C 3 4 | Q 1 4

输出:

2
1

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

上一题