/ Vijos / 题库 /

渡河

渡河

描述

传说中教主乃世外高人,不屑于参加OI竞赛,于是云游四方,威风八面。只不过教主行踪不定,就像传说中的神兽一样可遇而不可求。小L和小H为了求得教主签名的Orz教主T-Shirt,打算碰碰运气展开了冒险。在冒险中,他们不幸被突来的洪水冲到了一个神秘丛林中,他们想尽快逃出这个地方。小L找到了一张看似为曾经的冒险者遗弃的地图,但经过探查,地图所示的确实是这片丛林。小L从地图上看到,有众多河流穿过这片丛林,等到他接近一条最近的河流时,发现水流较急,且河水很深,小H不擅长游泳,所以他们决定利用丛林中的树木做一只竹筏渡河。

虽然竹筏做好后可以在这一条河所连通的水域任意行进,但是竹筏在上岸后必须抛弃,若想再次渡河必须再做一次竹筏,但这毕竟是十分辛苦的,他们希望做竹筏也就是渡河的次数尽量少,就求助于你。

地图上的陆地和河流可以抽象成一个n*n由数字0和1组成的矩阵,其中0代表陆地,1代表河流。无论在陆地上还还是河流上,他们都可以向相邻8格(边相邻或角相邻)移动,但是若要从陆地进入河流(也就是从0到1),则必须制作竹筏。若到达地图边界则顺利逃脱。但是小T和小K有可能迷路,所以会多次询问你,对于每次询问,只要输出到达地图边界需要的最少渡河次数即可,保证每次询问都是指向陆地。

小L和小H翻到地图的反面,赫然发现六个大字:“教主到此一游”!两人无法抑制自己激动的心情,将这张地图珍藏起来。据说后来这张图成为无价之宝。

格式

输入格式

第1行包括2个正整数N,K,分别描述了地图的长宽以及询问的次数。

下面N行,每行N个数字0或者1,数字之间没有空格,描述了这张地图。

接下来K行,每行2个正整数xi,yi,询问在第xi行第yi列最少需要渡河几次。

输出格式

输出仅包括1行,按输入顺序每行对于一个询问输出最少需要渡河的次数,数字间用空格隔开,行末换行并没有空格。

样例1

样例输入1

9 3
000000000
011111110
010101010
011000110
010000010
010111010
010101010
011111110
000000000
1 3
3 3
4 6

样例输出1

0 1 1

限制

对于20%的数据,有n≤10;
对于40%的数据,有n≤100,k≤10;
对于60%的数据,有n≤1000,k≤100;
对于100%的数据,有n≤1000,k≤40000。

时限1s

提示

第1次询问由于已经处于边界所以答案为0。

第2次询问不断向左或向上走都只要渡河1次。

第3次询问不断向四个方向中的一个方向走同样只需要1次渡河。

来源

TangKy

信息

ID
1468
难度
8
分类
搜索 | 数据结构 | 并查集 点击显示
标签
递交数
563
已通过
84
通过率
15%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

Orz教主第2次模拟赛