TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1234
  • 题目
  • P1234波速
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

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

    输入格式

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

    输出格式

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

    样例输入

    5 5 3
    abbaa
    abbaa
    aaaaa
    aaaaa
    aaaaa
    1 2
    1 4
    3 2

    样例输出

    1
    1
    3

    提示

    对于30%的数据,有1 ≤ N ≤ 50,1 ≤ Q ≤ 500;
    对于100%的数据,有1 ≤ N ≤ 1000,1 ≤ Q ≤ 100000。