fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef pair<int,int> p;
  6.  
  7. int n,m,k;
  8.  
  9. int dx[4] = {1,-1,0,0};
  10. int dy[4] = {0,0,1,-1};
  11.  
  12. char museum[1007][1007];
  13. bool visited[1007][1007];
  14.  
  15. long long pic;
  16.  
  17. long long int dp[1007][1007];
  18.  
  19. vector<p> connected;
  20.  
  21. void dfs(int x, int y){
  22. if(dp[x][y]!=-1){
  23. pic = dp[x][y];
  24. //cout<<"Hurray"<<endl;
  25. return;
  26. }
  27.  
  28. if(!visited[x][y] && museum[x][y] == '.'){
  29. //cout<<x<<" "<<y<<endl;
  30. connected.push_back(make_pair(x,y));
  31. visited[x][y] = true;
  32.  
  33. for(int k=0; k<4; k++){
  34. int nextX = x + dx[k];
  35. int nextY = y + dy[k];
  36. if(museum[nextX][nextY]=='*')
  37. pic++;
  38. if(nextX>0 && nextX<=n && nextY>0 && nextY<=m){
  39. dfs(nextX,nextY);
  40. }
  41. }
  42. }
  43. }
  44.  
  45. int main(){
  46. cin>>n>>m>>k;
  47.  
  48. for(int i=0; i<1007; i++){
  49. for(int j=0; j<1007; j++){
  50. dp[i][j] = -1;
  51. }
  52. }
  53.  
  54. for(int i=1; i<=n; i++){
  55. for(int j=1; j<=m; j++){
  56. cin>>museum[i][j];
  57. }
  58. }
  59.  
  60. long long ans = 0;
  61. for(int i=0; i<k; i++){
  62. connected.clear();
  63. for(int j=1; j<=n; j++){
  64. for(int z = 1; z<=m; z++)
  65. visited[j][z] = false;
  66. }
  67.  
  68. int x,y;
  69. cin>>x>>y;
  70. pic = 0;
  71. dfs(x,y);
  72. //cout<<"Done until here"<<endl;
  73. for(int j=0; j<connected.size(); j++){
  74. dp[connected[j].first][connected[j].second] = pic;
  75. }
  76.  
  77. cout<<pic<<endl;
  78. }
  79.  
  80. return 0;
  81. }
Success #stdin #stdout 0s 13320KB
stdin
Standard input is empty
stdout
Standard output is empty