E
给你一个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
思路：这个题dfs，bfs都可以写，我用的是bfs.博物馆中每个相连的空地可以是一部分，用一个计数器给这些部分做标记，并用vectory存放第几部分可以看到几副画，bfs搜索这些部分可以看到几幅画。bfs时只需要在搜索时遇到墙了就ans加一。注意题目给出的数很大，
注意超时。
1 #include <cstdio> 2 #include <fstream> 3 #include <algorithm> 4 #include <cmath> 5 #include <deque> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <cstring> 10 #include <map> 11 #include <stack> 12 #include <set> 13 #include <sstream> 14 #include <iostream> 15 #define mod 1000000007 16 #define ll long long 17 using namespace std; 18 19 int n,m,k; 20 string bwg[1005]; 21 int bj[1005][1005]; 22 vector<int> ve; 23 int fx[4]={1,-1,0,0},fy[4]={0,0,1,-1}; 24 typedef pair<int,int> pa; 25 pa no,s; 26 void bfs(int t) 27 { 28 queue<pa> qu; 29 qu.push(no); 30 int ans=0; 31 while(!qu.empty()) 32 { 33 no=qu.front(); 34 qu.pop(); 35 for(int i=0;i<4;i++) 36 { 37 int x=no.first+fx[i]; 38 int y=no.second+fy[i]; 39 if(x>=0&&x<n&&y>=0&&y<m&&bj[x][y]==0) 40 { 41 if(bwg[x][y]=='*') 42 { 43 ans++; 44 } 45 if(bwg[x][y]=='.') 46 { 47 s.first=x; 48 s.second=y; 49 bwg[x][y]='*'; 50 qu.push(s); 51 bj[x][y]=t; 52 } 53 } 54 } 55 } 56 ve.push_back(ans); 57 } 58 int main() 59 { 60 scanf("%d %d %d",&n,&m,&k); 61 for(int i=0;i<n;i++) 62 { 63 cin>>bwg[i]; 64 } 65 memset(bj,0,sizeof(bj)); 66 int id=1; 67 ve.push_back(0); 68 for(int i=0;i<n;i++) 69 { 70 for(int j=0;j<m;j++) 71 { 72 if(bwg[i][j]=='.') 73 { 74 no.first=i; 75 no.second=j; 76 bwg[i][j]='*'; 77 bj[i][j]=id; 78 bfs(id); 79 id++; 80 } 81 } 82 } 83 int x,y; 84 for(int i=0;i<k;i++) 85 { 86 scanf("%d %d",&x,&y); 87 printf("%d ",ve[bj[x-1][y-1]]); 88 } 89 90 }