08770. 拼豆画布 · 林老师的题库

题目描述

手工社的拼豆画框是一块 $n \times n$ 的方格画布，每个格子里放一颗拼豆：深色豆记作 $1$ ，浅色豆记作 $0$ 。装进玻璃框之前要给拼豆「定型」：上下左右相邻且颜色相同的拼豆会被胶水粘成同一片区域，斜对角的拼豆不算相邻。

现在有 $q$ 位同学依次来询问：第 $i$ 行第 $j$ 列那颗拼豆所在的区域，一共粘了多少颗拼豆？

第一行两个整数 $n, q$ （ $1 \leq n \leq 1000$ ， $1 \leq q \leq 100000$ ）。

接下来 $n$ 行，每行一个长度为 $n$ 的 01 字符串，表示画布。

接下来 $q$ 行，每行两个整数 $i, j$ （ $1 \leq i, j \leq n$ ），表示一次询问。

共 $q$ 行，每行一个整数：被询问的拼豆所在区域的拼豆总数。

输入

输出

4
11
6

样例解释：左上角 $2 \times 2$ 的浅色豆连成 $4$ 颗的一片； $(2, 5)$ 所在的浅色区域从第 $1$ 行一直绕到第 $5$ 行，共 $11$ 颗； $(5, 1)$ 所在的深色区域共 $6$ 颗。

对于 $100%$ 的数据： $1 \leq n \leq 1000$ ， $1 \leq q \leq 100000$ ，画布字符只有 $0$ 和 $1$ 。

本题共 $10$ 个测试点，每个测试点 $10$ 分。