Description
传说中教主乃世外高人，不屑于参加OI竞赛，于是云游四方，威风八面。只不过教主行踪不定，就像传说中的神兽一样可遇而不可求。小L和小H为了求得教主签名的Orz教主T-Shirt，打算碰碰运气展开了冒险。在冒险中，他们不幸被突来的洪水冲到了一个神秘丛林中，他们想尽快逃出这个地方。小L找到了一张看似为曾经的冒险者遗弃的地图，但经过探查，地图所示的确实是这片丛林。小L从地图上看到，有众多河流穿过这片丛林，等到他接近一条最近的河流时，发现水流较急，且河水很深，小H不擅长游泳，所以他们决定利用丛林中的树木做一只竹筏渡河。
虽然竹筏做好后可以在这一条河所连通的水域任意行进，但是竹筏在上岸后必须抛弃，若想再次渡河必须再做一次竹筏，但这毕竟是十分辛苦的，他们希望做竹筏也就是渡河的次数尽量少，就求助于你。
地图上的陆地和河流可以抽象冲一个n*n由数字0和1组成的矩阵，其中0代表陆地，1代表河流。无论在陆地上还还是河流上，他们都可以向相邻8格（边相邻或角相邻）移动，但是若要从陆地进入河流（也就是从0到1），则必须制作竹筏。若到达地图边界则顺利逃脱。但是小T和小K有可能迷路，所以会多次询问你，对于每次询问，只要输出到达地图边界需要的最少渡河次数即可，保证每次询问都是指向陆地。
小L和小H翻到地图的反面，赫然发现六个大字：“教主到此一游”！两人无法抑制自己激动的心情，将这张地图珍藏起来。据说后来这张图成为无价之宝。
Input
第1行包括2个正整数N，K，分别描述了地图的长宽以及询问的次数。
下面N行，每行N个数字0或者1，数字之间没有空格，描述了这张地图。
接下来K行，每行2个正整数xi，yi，询问在第xi行第yi列最少需要渡河几次。
Output
输出仅包括1行，按输入顺序每行对于一个询问输出最少需要渡河的次数，数字间用空格隔开，行末换行并没有空格。
Sample Input
9 3
000000000
011111110
010101010
011000110
010000010
010111010
010101010
011111110
000000000
1 3
3 3
4 6
Sample Output
0 1 1
Data Constraint
Hint
【样例说明】
第1次询问由于已经处于边界所以答案为0。
第2次询问不断向左或向上走都只要渡河1次。
第3次询问不断向四个方向中的一个方向走同样只需要1次渡河。
【数据规模】
对于20%的数据，有n≤10；
对于40%的数据，有n≤100，k≤10；
对于60%的数据，有n≤1000，k≤100；
对于100%的数据，有n≤1000，k≤40000。
题解：
本题一看就是用预处理的方法去做。
看看题意，才发现走到边界就可以逃离。那么，就直接把边界各个点的花费改成0，若是边界是水，就改成1.然后在寻找每个点，寻找这个点的八个方向。若是这个点是陆地，那么找这个点八方的水的花费，若是这个点是水路，那么就找这个点的八方的陆地花费。然后就把这个点可以连到且数字一样的数都改成这个花费，于是就对了。
标程：
type
new=record
x:longint;
y:longint;
z:longint;
end;
var
i,j,k,l,n,m,head,tail,took,x,y,cs:longint;
a:array[1..1000000] of new;
map,land,river:array[1..1000,1..1000] of longint;
bz:array[1..1000,1..1000] of boolean;
fx:array[1..8,1..2] of longint=((-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1));
s:ansistring;
procedure riverbfs(dep:longint);
var
i,j,k,l,nx,ny:longint;
begin
for i:=1 to 8 do
begin
nx:=a[dep].x+fx[i,1];
ny:=a[dep].y+fx[i,2];
if(nx>0)and(nx<=n)and(ny>0)and(ny<=n) then
begin
if (bz[nx,ny])and(map[nx,ny]=1) then
begin
inc(took);
a[took].x:=nx;
a[took].y:=ny;
bz[nx,ny]:=false;
river[nx,ny]:=cs;
end;
end;
end;
end;
procedure landbfs(dep:longint);
var
i,j,k,l,nx,ny:longint;
begin
for i:=1 to 8 do
begin
nx:=a[dep].x+fx[i,1];
ny:=a[dep].y+fx[i,2];
if(nx>0)and(nx<=n)and(ny>0)and(ny<=n) then
begin
if (bz[nx,ny])and(map[nx,ny]=0) then
begin
inc(took);
a[took].x:=nx;
a[took].y:=ny;
bz[nx,ny]:=false;
land[nx,ny]:=cs;
end;
end;
end;
end;
begin
//assign(input,'cross_the_river.in');reset(input);
readln(n,m);
fillchar(bz,sizeof(bz),true);
for i:=1 to n do
begin
readln(s);
for j:=1 to n do
begin
if s[j]='1' then inc(map[i,j]);
end;
end;
for i:=1 to n do
begin
if map[1,i]=0 then
begin
head:=1;tail:=1;took:=1;
a[1].x:=1;
a[1].y:=i;
land[1,i]:=cs;
bz[i,1]:=false;
repeat
for j:=head to tail do
landbfs(j);
head:=tail+1;
tail:=took;
until head>tail;
end;
if map[n,i]=0 then
begin
head:=1;tail:=1;took:=1;
a[1].x:=n;
a[1].y:=i;
land[n,i]:=cs;
bz[i,1]:=false;
repeat
for j:=head to tail do
landbfs(j);
head:=tail+1;
tail:=took;
until head>tail;
end;
if map[i,1]=0 then
begin
head:=1;tail:=1;took:=1;
a[1].x:=i;
a[1].y:=1;
land[i,1]:=cs;
bz[i,1]:=false;
repeat
for j:=head to tail do
landbfs(j);
head:=tail+1;
tail:=took;
until head>tail;
end;
if map[i,n]=0 then
begin
head:=1;tail:=1;took:=1;
a[1].x:=i;
a[1].y:=n;
land[i,n]:=cs;
bz[i,1]:=false;
repeat
for j:=head to tail do
landbfs(j);
head:=tail+1;
tail:=took;
until head>tail;
end;
end;
cs:=1;
for i:=1 to n do
begin
if map[1,i]=1 then
begin
head:=1;tail:=1;took:=1;
a[1].x:=1;
a[1].y:=i;
river[1,i]:=cs;
bz[i,1]:=false;
repeat
for j:=head to tail do
riverbfs(j);
head:=tail+1;
tail:=took;
until head>tail;
end;
if map[n,i]=1 then
begin
head:=1;tail:=1;took:=1;
a[1].x:=n;
a[1].y:=i;
river[n,i]:=cs;
bz[i,1]:=false;
repeat
for j:=head to tail do
riverbfs(j);
head:=tail+1;
tail:=took;
until head>tail;
end;
if map[i,1]=1 then
begin
head:=1;tail:=1;took:=1;
a[1].x:=i;
a[1].y:=1;
river[i,1]:=cs;
bz[i,1]:=false;
repeat
for j:=head to tail do
riverbfs(j);
head:=tail+1;
tail:=took;
until head>tail;
end;
if map[i,n]=1 then
begin
head:=1;tail:=1;took:=1;
a[1].x:=i;
a[1].y:=n;
river[i,n]:=cs;
bz[i,1]:=false;
repeat
for j:=head to tail do
riverbfs(j);
head:=tail+1;
tail:=took;
until head>tail;
end;
end;
cs:=0;
for i:=2 to n-1 do
begin
for j:=2 to n-1 do
begin
if bz[i,j] then
begin
if map[i,j]=0 then
begin
for k:=1 to 8 do
begin
x:=i+fx[k,1];
y:=j+fx[k,2];
if river[x,y]>0 then cs:=river[x,y]
else if (river[x,y]<cs)and(river[x,y]>0) then cs:=river[x,y];
end;
head:=1;tail:=1;took:=1;
a[1].x:=i;
a[1].y:=j;
land[i,j]:=cs;
bz[i,j]:=false;
repeat
for k:=head to tail do
landbfs(k);
head:=tail+1;
tail:=took;
until head>tail;
end
else
begin
for k:=1 to 8 do
begin
x:=i+fx[k,1];
y:=j+fx[k,2];
if land[x,y]>0 then cs:=land[x,y]
else if (land[x,y]<cs)and(land[x,y]>0) then cs:=land[x,y];
end;
head:=1;tail:=1;took:=1;
a[1].x:=i;
a[1].y:=j;
river[i,j]:=cs+1;
inc(cs);
bz[i,j]:=false;
repeat
for k:=head to tail do
riverbfs(k);
head:=tail+1;
tail:=took;
until head>tail;
end;
end;
end;
end;
for i:=1 to m do
begin
readln(x,y);
write(land[x,y],' ');
end;
writeln;
end.