#P4437. [Cerc2015]Looping Labyrinth

    ID: 3642 传统题 1000ms 512MiB 尝试: 37 已通过: 13 难度: 8 上传者: 标签>CF2500省选/NOI-广度优先搜索扩展欧几里得算法欧几里得算法二维整数格基维护

[Cerc2015]Looping Labyrinth

题目描述

一座迷宫是由一个矩形网格铺上一种图案得到的。矩形网格有 nn 行 mm 列,每一个格子不是空的就是被覆盖的。如此就形成了一个无穷大的网格,且图案向四个方向无限循环。

我们给每个格子编号(包括负整数),行数向下递增,列数向右递增,座标为 (0,0)(0, 0) 的单元格为原点。整个迷宫由复制图案到每个 n×mn \times m 的矩阵而成(没有旋转和镜像操作)。每个图案的左上角的单元格的行数可被 nn 整除,列数可被 mm 整除。原图案的左上角位于原点,右下角的座标为 (n−1,m−1)(n-1, m-1)。

我们需从一个单元格出发,向上、下、左、右移动,经过一些空格,到达原点。

你将被给出一个图案和一些出发点。确定从这些出发点出发是否能逃出迷宫。

输入格式

第一行包括 22 个整数 nn 和 mm——图案的行数和列数。

接下来 nn 行每行包括一个长度为 mm 的字符串,表示图案的一行。

# 表示一个被覆盖的单元格,. 表示未被覆盖的单元格。

接下来一行包括一个整数 qq ——出发点的个数。

接下来 qq 行,每行包括两个整数 rr 和 cc——出发点的座标。

原点和所有出发点都是空单元格。

输出格式

输出包括 qq 行。

对每个出发点,如果能过逃出迷宫,输出 yes,否则输出 no。

6 9
..#####..
..#...#.. 
......#.. 
..#####.. 
..#...... 
..#...#.. 
5
1 4
5 4
1 -5
5 -5
-1000000000 0
yes
no
no
yes
yes

数据规模与约定

对于 100%100 \% 的数据,1≤n,m≤1001 \le n, m \le 100,−109≤r,c≤109-10^9 \le r, c \le 10^9。