问题说明

相传在恒河之滨，每当半夜子时，山上有一处会有亮光。当地人称有仙人在山中。一外地探宝家慕名而至，经过长期观察，的确发现每当半夜子时，山上会有亮光出现。
一天他约了几个同行一起向山里进发，他们在一个非常隐蔽处发现了一个洞，进入洞口后有一个n×n格子阵当在他们面前，而且必须通过该阵。每个格子由活动的方石组成，每一个方石上刻着符号看上去像0,1两种，由于该石阵的方石每隔一段时间会变换位置(真神奇！！)，当然都在n×n格子阵中，所以他们必须在短时间内知道他们是否能安全通过。
通过规则：
若你位于一格0上（不一定是第一个格子开始噢！），那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上，不可以重复走已经走过的方格。
走过的格子超过所有格子的一半，石阵就不会变化能安全通过了。
作为一个位编程高手的你，出手了！帮助他们计算每次石阵变化后按给定的坐标开始能走几格？

输入格式

第1行为两个正整数n,m。
下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。
接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。

输出格式

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

2 2
01
10
1 1
2 2

4
4

提示

所有格子互相可达。

对于20%的数据，n≤10；

对于40%的数据，n≤50；

对于50%的数据，m≤5；

对于60%的数据，n≤100,m≤100；

对于100%的数据，n≤1000,m≤100000。

来源/分类

数据结构