[BFS]Codeforces Igor In the Museum

Igor is in the museum and he wants to see as many pictures as possible.

Museum can be represented as a rectangular field of n × m cells. Each cell is either empty or impassable. Empty cells are marked with '.', impassable cells are marked with '*'. Every two adjacent cells of different types (one empty and one impassable) are divided by a wall containing one picture.

At the beginning Igor is in some empty cell. At every moment he can move to any empty cell that share a side with the current one.

For several starting positions you should calculate the maximum number of pictures that Igor can see. Igor is able to see the picture only if he is in the cell adjacent to the wall with this picture. Igor have a lot of time, so he will examine every picture he can see.

Input

First line of the input contains three integers n, m and k(3 ≤ n, m ≤ 1000, 1 ≤ k ≤ min(n·m, 100 000)) — the museum dimensions and the number of starting positions to process.

Each of the next n lines contains m symbols '.', '*' — the description of the museum. It is guaranteed that all border cells are impassable, so Igor can't go out from the museum.

Each of the last k lines contains two integers x and y (1 ≤ x ≤ n, 1 ≤ y ≤ m) — the row and the column of one of Igor's starting positions respectively. Rows are numbered from top to bottom, columns — from left to right. It is guaranteed that all starting positions are empty cells.

Output

Print k integers — the maximum number of pictures, that Igor can see if he starts in corresponding position.

Examples

input

Copy

5 6 3
******
*..*.*
******
*....*
******
2 2
2 5
4 3

output

Copy

6
4
10

input

Copy

4 4 1
****
*..*
*.**
****
3 2

output

Copy

题意:

在一个有n*m的格子（这些格子是矩形且每个格子与周围的4个格子邻接）平面内，能走的格子为'.',不能走的格子为'#'称为墙，有多个起点，问若从一个起点出发，能找到多少与墙相邻的边

思路:

先读入整个地图
注意要先把整个地图读完在看墙的上下左右，因为如果边度边判断就无法判断下面和右边的情况（你还没读到，现在是不存在的）
如果当前这个是墙，则其上下左右在n*m的格子内的可走区域的答案要+1
接着读入起始点
若这个格子以前被走过了就直接输出答案
否则就从这个格子开始搜索并把一开始处理好的墙边上可走的格子的答案加上，并把当前能走到的点都更新为这个答案，因为从这些点出发都能得到这个最大答案

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int amn=1e3+5;
 4 char mp[amn][amn];
 5 long long ans[amn][amn],n,m,k,as,sx,sy;
 6 bool idx[amn][amn],f[amn][amn];
 7 int dic[10][5]={{0,-1},{0,+1},{+1,0},{-1,0}};
 8 struct node{
 9     int x;int y;
10 };
11 queue<node> q;
12 long long fd(int x,int y){
13     node a;
14     a.x=x;a.y=y;
15     while(q.size())q.pop();
16     q.push(a);
17     long long cnt=0;
18     while(q.size()){
19         node w=q.front();q.pop();
20         //cout<<w.x<<'!'<<w.y<<endl;
21         f[w.x][w.y]=idx[w.x][w.y]=1;
22         if(ans[w.x][w.y])cnt+=ans[w.x][w.y];
23         for(int k=0;k<4;k++){
24             int dx=w.x+dic[k][0];
25             int dy=w.y+dic[k][1];
26             //cout<<k<<' '<<w.x<<' '<<w.y<<' '<<dx<<'@'<<dy<<' '<<cnt<<endl;
27             if(dx>1&&dx<n&&dy>1&&dy<m&&mp[dx][dy]=='.'&&!idx[dx][dy]&&!f[dx][dy]){
28                     f[dx][dy]=idx[dx][dy]=1;
29                     a.x=dx;a.y=dy;
30                     q.push(a);
31             }
32         }
33     }
34     return cnt;
35 }
36 void cg(int x,int y,long long val){
37     node a;
38     a.x=x;a.y=y;
39     while(q.size())q.pop();
40     q.push(a);
41     while(q.size()){
42         node w=q.front();q.pop();
43         //cout<<w.x<<'?'<<w.y<<endl;
44         idx[w.x][w.y]=0;
45         ans[w.x][w.y]=val;
46         for(int k=0;k<4;k++){
47             int dx=w.x+dic[k][0];
48             int dy=w.y+dic[k][1];
49             if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&mp[dx][dy]=='.'&&idx[dx][dy]&&f[dx][dy]){
50                     idx[dx][dy]=0;          ///idx是搜索标记，注意只有idx还原为0，f数组是看这个答案是否存在，只要有答案就不需要更改了
51                     a.x=dx;a.y=dy;
52                     q.push(a);
53             }
54         }
55     }
56 }
57 int main(){
58     ios::sync_with_stdio(0);
59     cin>>n>>m>>k;
60     for(int i=1;i<=n;i++)
61         for(int j=1;j<=m;j++)
62             f[i][j]=idx[i][j]=ans[i][j]=0;
63     for(int i=1;i<=n;i++){
64         for(int j=1;j<=m;j++){
65             cin>>mp[i][j];              ///先读入整个地图
66         }
67     }
68     for(int i=1;i<=n;i++){
69         for(int j=1;j<=m;j++){          ///注意要先把整个地图读完在看墙的上下左右，因为如果边度边判断就无法判断下面和右边的情况（你还没读到，现在是不存在的）
70             if(mp[i][j]=='*'){          ///如果当前这个是墙，则其上下左右在n*m的格子内的可走区域的答案要+1
71                 for(int k=0;k<4;k++){   
72                     int dx=i+dic[k][0];
73                     int dy=j+dic[k][1];
74                     if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&mp[dx][dy]=='.')ans[dx][dy]++;//cout<<dx<<' '<<dy<<' '<<ans[dx][dy]<<endl;;
75                 }
76             }
77         }
78     }
79     while(k--){
80         cin>>sx>>sy;
81         if(f[sx][sy])printf("%lld\n",ans[sx][sy]);      ///若这个格子以前被走过了就直接输出答案
82         else{                                           ///否则就从这个格子开始搜索并把一开始处理好的墙边上可走的格子的答案加上，并把当前能走到的点都更新为这个答案，因为从这些点出发都能得到这个最大答案
83             as=fd(sx,sy);
84             cg(sx,sy,as);
85             printf("%lld\n",ans[sx][sy]);
86         }
87     }
88 }
89 /***
90 在一个有n*m的格子（这些格子是矩形且每个格子与周围的4个格子邻接）平面内，能走的格子为'.',不能走的格子为'#'称为墙，有多个起点，问若从一个起点出发，能找到多少与墙相邻的边
91 先读入整个地图
92 注意要先把整个地图读完在看墙的上下左右，因为如果边度边判断就无法判断下面和右边的情况（你还没读到，现在是不存在的）
93 如果当前这个是墙，则其上下左右在n*m的格子内的可走区域的答案要+1
94 接着读入起始点
95 若这个格子以前被走过了就直接输出答案
96 否则就从这个格子开始搜索并把一开始处理好的墙边上可走的格子的答案加上，并把当前能走到的点都更新为这个答案，因为从这些点出发都能得到这个最大答案
97 ***/