P3820 小D的地下温泉

    • 81通过
    • 886提交
  • 题目提供者 FlierKing 管理员
  • 评测方式 云端评测
  • 标签 并查集 广度优先搜索,BFS 连通块 洛谷原创
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    小D最喜欢泡温泉了。小D找某奸商租下了一块 $N$ 行 $M$ 列的地,左上角为 $(1,1)$ ,右下角为 $(N,M)$ 。小D本以为这块地里全是温泉,结果这块地极不稳定,曾经发生过一些地形变动,所以其中一些地方全是土。

    题目描述

    一开始他会告诉你当前这块地的情况,但是小D有一些假操作,希望你操作给他看:

    1. 由小D指定 $w$ 个位置,他希望知道其中哪个位置下水泡温泉的范围最大。泡温泉的范围定义为指定位置通过向上下左右四个方向能到达的位置的个数。若询问的位置为土,则范围为0。如果如果有多个位置均为最大,输出给出顺序较前的那个。位置编号为 $1,2,...,w$ 。

    2. 由小D指定 $w$ 个位置,他会使用膜法按顺序翻转这 $w$ 个地方的地形。即若原位置是土,则该位置变为温泉;若原位置是温泉,则该位置变为土。因为小D不希望活动范围减少得太快,所以他在将温泉变为土时不会将一个区域分割。

    输入输出格式

    输入格式:

    第一行输入两个整数, $N,M$ ,为土地大小。

    接下来的 $N$ 行每行输入 $M$ 个字符,为'.'(代表温泉)或'*'(代表土)(不包括引号)

    第 $N+2$ 行输入一个整数, $Q$ ,为操作数量。

    接下来的 $Q$ 行,每行先读入两个整数 $opt$ 和 $w$ ,表示操作类型和指定点的数量,在同一行还有 $2\times w$ 个数 $x_{1},y_{1},x_{2},y_{2},...,x_{w},y_{w}$ ,分别表示 $w$ 个操作的位置为 $(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{w},y_{w})$ 。

    输出格式:

    对于每个操作1,输出询问的答案并换行

    输入输出样例

    输入样例#1: 复制
    5 5
    .*...
    .****
    *....
    *****
    .....
    3
    1 2 1 1 1 3
    2 1 3 1
    1 2 1 1 1 3
    输出样例#1: 复制
    2
    1
    

    说明

    对于30%的数据, $N,M\le 100,\sum w\le 100$

    对于70%的数据, $N,M\le 1000$

    对于100%的数据, $1\le N\times M,Q\le 10^{6},\sum w\le 10^{6},w\geq 1$

    数据在windows下制作

    标程展开

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。