P74177

01迷宫

难度 4 级 小学 算法入门 BFS 搜索 回溯
讨论 统计 12通过 24提交 50%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

有一个仅由数字 0 与 1 组成的 n \times n 格迷宫。若你位于一格 0 上,那么你可以移动到相邻 4 格中的某一格 1 上,同样若你位于一格 1 上,那么你可以移动到相邻 4 格中的某一格 0 上。

你的任务是:对于给定的迷宫,询问从某一格开始能移动到多少个格子(包含自身)。

输入

第一行为两个正整数 n,m。

下面 n 行,每行 n 个字符,字符只可能是 0 或者 1,字符之间没有空格。

接下来 m 行,每行两个用空格分隔的正整数 i,j,对应了迷宫中第 i 行第 j 列的一个格子,询问从这一格开始能移动到多少格。

输出

m 行,对于每个询问输出相应答案。

样例

样例 1
输入
2 2
01
10
1 1
2 2
输出
4
4

提示

  • 对于 100\% 的数据,1\le n \leq 1000,1\le m \leq 100000。
Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交