Igor In the Museum

Descriptions

给你一个n*m的方格图表示一个博物馆的分布图.

每个方格上用'*'表示墙,用'.'表示空位.

每一个空格和相邻的墙之间都有一幅画.

(相邻指的是上下左右相邻).

你可以从一个空格的位置走到相邻的空格位置.

现在你给你若干个(xi,yi)形式的询问,表示你现在在(xi,yi)这个位置(保证为空位)出发,问你从这个点出发你能看到多少幅画.

Input

第一行有3个整数n,m,k(3<=n,m<=1000,1<=k<=min(m*m,100000) ).

接下来有n行每行m个字符,每个字符为'.'或者'*'.

紧接着k行,每行两个整数xi,yi.

Output

对于k个询问,输出相应的答案.

Examples

Input

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

Output

6 4 10

Input

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

Output
8

题目链接

不难的一个bfs，一直t在memset上，每次bfs是不需要memset标记数组的，只要你记录一下，每个点就只需要扫一次了，直接一整个幅地图按块bfs，即从这一块的"."出发，看到的都是ans副画，并且记录下来，最后直接输出即可。还不清楚可以参考代码

AC代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   #define IOS ios_base::sync_with_stdio(0); cin.tie(0);#define Mod 1000000007#define eps 1e-6#define ll long long#define INF 0x3f3f3f3f#define MEM(x,y) memset(x,y,sizeof(x))#define Maxn 1005using namespace std;int n,m,k;char mp[Maxn][Maxn];//存图int vis[Maxn][Maxn];//标记"."是否走过int step;//几副画int dt[][2]= { { 0,1},{ 0,-1},{ 1,0},{-1,0}};//四个方向struct node{ int x,y;};node now,net;node road[1000005];//"."这个点的状态int ans[Maxn][Maxn];//记录从(x,y)能看到几幅画void judge(int x,int y)//(x,y)这四周有几幅画{ for(int i=0; i<4; i++) { int tx=dt[i][0]+x; int ty=dt[i][1]+y; if(tx>=1&&ty>=1&&tx<=n&&ty<=m&&mp[tx][ty]=='*') { step++; } }}void bfs(){ step=0;//几幅画 int cnt=0;//第几个"." queue
                   
                    q; q.push(now); judge(now.x,now.y); vis[now.x][now.y]=1; while(!q.empty()) { now=q.front(); q.pop(); road[cnt++]=now; for(int i=0; i<4; i++)//四个方向bfs { int tx=dt[i][0]+now.x; int ty=dt[i][1]+now.y; if(tx>=1&&ty>=1&&tx<=n&&ty<=m&&!vis[tx][ty]&&mp[tx][ty]=='.') { net.x=tx,net.y=ty; q.push(net); judge(tx,ty); vis[tx][ty]=1; } } } for(int i=0; i
                    
                     >n>>m>>k; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin>>mp[i][j]; for(int i=1; i<=n; i++)//开始一块一块的找"."并且bfs { for(int j=1; j<=m; j++) { if(mp[i][j]=='.'&&!vis[i][j]) { now.x=i,now.y=j; bfs(); } } } while(k--) { int x,y; cin>>x>>y; cout<
                     
                      <

转载于:https://www.cnblogs.com/sky-stars/p/11223374.html

你可能感兴趣的文章