fork(3) download
copy 
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<cmath>
  4. #include<cstdlib>
  5. #include<cstdio>
  6. #include<ctime>
  7. #include<cctype>
  8. #include<cassert>
  9. #include<climits>
  10. #include<cerrno>
  11. #include<cfloat>
  12. #include<ciso646>
  13. #include<clocale>
  14. #include<csetjmp>
  15. #include<csignal>
  16. #include<cstdarg>
  17. #include<cstddef>
  18. #include<cstdio>
  19. #include<cstdlib>
  20. #include<cstring>
  21. #include<ctime>
  22. #include<cwchar>
  23. #include<cwctype>
  24.  
  25. //containers
  26. #include<vector>
  27. #include<list>
  28. #include<map>
  29. #include<queue>
  30. #include<deque>
  31. #include<set>
  32. #include<complex>
  33. #include<string>
  34. #include<stack>
  35. #include<bitset>
  36. #include<istream>
  37. #include<valarray>
  38.  
  39. //IOs
  40. #include<iostream>
  41. #include<sstream>
  42. #include<iomanip>
  43. #include<fstream>
  44. #include<exception>
  45. #include<ios>
  46. #include<iosfwd>
  47. #include<ostream>
  48. #include<iterator>
  49. #include<stdexcept>
  50. #include<streambuf>
  51.  
  52.  
  53. //algorithm & miscellaneous
  54. #include<algorithm>
  55. #include<functional>
  56. #include<numeric>
  57. #include<utility>
  58. #include<limits>
  59. #include<locale>
  60. #include<memory>
  61. #include<new>
  62.  
  63. #define pb push_back
  64.  
  65. using namespace std;
  66.  
  67. int prime[500];
  68. int r,c;
  69. int noofPrimes[500];
  70.  
  71. void sieve()
  72. {
  73. 	memset(prime,1,sizeof(prime));
  74. 	memset(noofPrimes,0,sizeof(noofPrimes));
  75. 	prime[0]=prime[1]=0;
  76. 	int count=0;
  77.  
  78. 	for(int i=2;i<=500;i++)
  79. 	{
  80. 		if(prime[i])
  81. 		{
  82. 			count++;
  83. 			for(int j=2*i;j<500;j+=i)
  84. 			prime[j]=0;
  85. 		}	
  86. 		noofPrimes[i]=count;
  87. 	}
  88.  
  89. }
  90.  
  91. int main()
  92. {
  93.     ////////////////////////////////////////////////////
  94. 	sieve();
  95. 	int t;
  96. 	scanf("%d",&t);
  97. 	while(t--)
  98. 	{
  99. 		int r,c;
  100. 		scanf("%d",&r);
  101. 		scanf("%d",&c);
  102. 		vector<string>a;
  103. 		for(int i=0;i<r;i++)
  104. 		{
  105. 			string st;
  106. 			cin>>st;
  107. 			a.pb(st);	
  108. 		}
  109.  
  110. 		int l[r][c],rt[r][c],u[r][c],d[r][c];
  111. 		memset(l,0,sizeof(l));	
  112. 		memset(rt,0,sizeof(rt));
  113. 		memset(u,0,sizeof(u));
  114. 		memset(d,0,sizeof(d));
  115.  
  116. 		for(int i=1;i<r;i++)
  117. 		{
  118. 			for(int j=1;j<c;j++)
  119. 			{
  120. 				if(a[i][j]=='#')
  121. 				{
  122. 					l[i][j]=0;
  123. 					u[i][j]=0;	
  124. 				}
  125. 				else
  126. 				{	
  127. 					if(a[i][j-1]=='^')
  128. 					l[i][j]=l[i][j-1]+1;
  129. 					else
  130. 					l[i][j]=0;
  131. 					if(a[i-1][j]=='^')
  132. 					u[i][j]=u[i-1][j]+1;
  133. 					else
  134. 					u[i][j]=0;
  135. 				}
  136. 			}	
  137. 		}
  138.  
  139. 		for(int i=r-2;i>=0;i--)
  140. 		{
  141. 			for(int j=c-2;j>=0;j--)
  142. 			{
  143. 				if(a[i][j]=='#')
  144. 				{
  145. 					rt[i][j]=0;
  146. 					d[i][j]=0;	
  147. 				}	
  148. 				else
  149. 				{
  150. 					if(a[i][j+1]=='^')
  151. 					rt[i][j]=rt[i][j+1]+1;
  152. 					else
  153. 					rt[i][j]=0;
  154. 					if(a[i+1][j]=='^')
  155. 					d[i][j]=d[i+1][j];
  156. 					else
  157. 					d[i][j]=0;	
  158. 				}
  159. 			}	
  160. 		}
  161. 		int ans=0;
  162. 		for(int i=0;i<r;i++)
  163. 		{
  164. 			for(int j=0;j<c;j++)
  165. 			{
  166. 				if(a[i][j]=='^')
  167. 				{
  168. 					int mini=min(l[i][j],rt[i][j]);
  169. 					mini=min(mini,d[i][j]);
  170. 					mini=min(mini,u[i][j]);
  171. 					if(mini>=2)
  172. 					{
  173. 						ans+=noofPrimes[mini];
  174. 						//cout<<"mini"<<i<<","<<j<<mini<<"\n";
  175. 					}
  176. 				}	
  177. 			}	
  178. 		}
  179.  
  180. 		cout<<ans<<"\n";
  181. 	}
  182.     ////////////////////////////////////////////////////
  183.  
  184.  
  185.     return 0;
  186.     }
  187.  
Success #stdin #stdout 0s 6652KB
comments (?)
stdin
copy 
2
3 10
#^^^^^#^##
^^^^^^^^^^
^^^^^^^^^#
7 10
^^^^#^^^^#
^^^^^^^^#^
^^##^^#^^^
#^^^^^^^#^
^^#^^^^^^^
^^^^#^^^^^
^^^^^^^^^^
stdout
copy 
0
0
https://ideone.com/7KMmIx
Codechef CAO2 test
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 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!