P2427 Wave

    • 48通过
    • 137提交
  • 题目提供者 曹彦臣
  • 评测方式 云端评测
  • 标签 搜索 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    波在不同的介质中的传播速度是不一样的。真空中波速都是3*108m/s,而在液体介质中的波速会比真空中的波速小,并且在不同的液体介质中波速不一样。我们将一个液体表面分成N * M块相同大小的正方形格子,每个格子中只包含一种液体介质。现在我们想知道,从某个波源传出去的波能以不变的波速延伸到多大的以波源为中心的大正方形内。假定所有大正方形的边都是平行于坐标轴的。

    输入输出格式

    输入格式:

    输入文件第一行包含三个整数N、M和Q,分别表示液体表面分成的正方形格子的行数和列数,以及询问的个数。接下来是一个N * M的矩阵,其中每个元素包含一个小写字母表示相应各自内的介质,不同的字母表示不同的介质。接下来Q行每行用两个数X和Y描述一个询问,表示询问以第X行第Y列为波源的波能以不变的波速延伸到的最大的以波源为中心的大正方形的边长。注意行的标号从0到N-1,列的标号从0到M-1。

    输出格式:

    输出文件包括Q行,每行包含一个整数,即相应问题的答案。

    输入输出样例

    输入样例#1: 复制
    5 5 3
    abbaa
    abbaa
    aaaaa
    aaaaa
    aaaaa
    1 2
    1 4
    3 2
    
    输出样例#1: 复制
    1
    1
    3
    

    说明

    对于30%的数据,有1 ≤ N,M ≤ 50,1 ≤ Q ≤ 500;

    对于100%的数据,有1 ≤ N,M≤ 1000,1 ≤ Q ≤ 10000。

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