fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Z0fT1R
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!