fork download
  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
stdin
2
3 10
#^^^^^#^##
^^^^^^^^^^
^^^^^^^^^#
7 10
^^^^#^^^^#
^^^^^^^^#^
^^##^^#^^^
#^^^^^^^#^
^^#^^^^^^^
^^^^#^^^^^
^^^^^^^^^^
stdout
0
0