P1141 01 Maze

There is an $n \times n$ grid maze consisting only of digits $0$ and $1$. If you are on a cell with $0$, you may move to one of the 4 adjacent cells with $1$. Similarly, if you are on a cell with $1$, you may move to one of the 4 adjacent cells with $0$. Your task is: for the given maze, for each specified starting cell, determine how many cells are reachable (including the starting cell).

The first line contains two positive integers $n,m$. The next $n$ lines each contain $n$ characters, each of which is either $0$ or $1$, with no spaces between characters. Then follow $m$ lines. Each line contains two positive integers $i,j$, referring to the cell at row $i$, column $j$ of the maze, asking how many cells are reachable starting from this cell.

Output $m$ lines. For each query, print the corresponding answer.

For the sample, all cells are mutually reachable. - For $20\%$ of the testdata, $n \leq 10$. - For $40\%$ of the testdata, $n \leq 50$. - For $50\%$ of the testdata, $m \leq 5$. - For $60\%$ of the testdata, $n,m \leq 100$. - For $100\%$ of the testdata, $1\le n \leq 1000$, $1\le m \leq 100000$. Translated by ChatGPT 5