1. /*
  2.   FORHAD-SUST-BD
  3. */
  4. #include <iostream>
  5. #include <string>
  6. #include <map>
  7. #include <queue>
  8. #include <stack>
  9. #include <algorithm>
  10. #include <list>
  11. #include <set>
  12. #include <cmath>
  13. #include <cstring>
  14. #include <stdio.h>
  15. #include <string.h>
  16. #include <sstream>
  17. #include <stdlib.h>
  18. #include <vector>
  19. #include <iomanip>
  20.  
  21. using namespace std;
  22.  
  23. #ifdef __GNUC__
  24. typedef long long ll;typedef unsigned long long ull;
  25. #else
  26. typedef __int64 ll; typedef unsigned __int64 ull;
  27. #endif
  28.  
  29. #define INF 1<<28
  30. #define SIZE 100
  31. #define PI 2*acos(0)
  32. #define fg %I64d
  33. #define REP(i,n) for (i=0;i<n;i++)
  34. #define REV(i,n) for (i=n;i>=0;i--)
  35. #define FOR(i,p,k) for (i=p; i<k;i++)
  36. #define FOREACH(it,x) for(__typeof((x).begin()) it=(x.begin()); it!=(x).end(); ++it)
  37.  
  38. #define bug(x) cout<< "->" <<#x<<": "<<x<<endl
  39. #define Sort(x) sort(x.begin(),x.end())
  40. #define Reverse(x) reverse(x.begin(),x.end())
  41. #define MP(a,b) make_pair(a,b)
  42. #define Clear(x,with) memset(x,with,sizeof(x))
  43. #define Copy(c,r) memcpy(c,r,sizeof(r))
  44. #define SZ(x) (int)x.size()
  45. #define length(x) (int)x.length()
  46. #define All(x) x.begin(),x.end()
  47. #define pb push_back
  48. #define popcount(i) __builtin_popcount(i)
  49. #define gcd(a,b) __gcd(a,b)
  50. #define fs first
  51. #define sc second
  52. #define two(X) (1<<(X))
  53. #define twoL(X) (((int64)(1))<<(X))
  54. #define contain(S,X) (((S)&two(X))!=0)
  55. #define containL(S,X) (((S)&twoL(X))!=0)
  56.  
  57. typedef pair<int,int> pii;
  58. typedef pair<double,double> pdd;
  59. typedef vector<int> vi;
  60. typedef vector<double>vd;
  61. typedef vector<ll>vll;
  62. typedef vector<string> vs;
  63. typedef vector<vi>vvi;
  64. typedef vector<vll>vvll;
  65. typedef vector<vd>vvd;
  66. typedef vector<pii>vpii;
  67. typedef map<string,int> msi;
  68. typedef map<int,int>mii;
  69. typedef map<pii,int>mpi;
  70.  
  71. template<class T> inline T sqr(T x){return x*x;}
  72. template<class T> inline bool isPrime(T n){if(n<=1)return false;for (T i=2;i*i<=n;i++) if (n%i==0) return false;return true;}
  73. template<class T> inline T Mod(T n,T m) {return (n%m+m)%m;} //For Positive Negative No.
  74. template<class T> string toString(T n){ostringstream oss;oss<<n;oss.flush();return oss.str();}
  75. int toInt(string s){int r=0;istringstream sin(s);sin>>r;return r;}
  76. ll toLl(string s){ll r=0;istringstream sin(s); sin>>r; return r;}
  77. template<class T> void debug(const T& e){cout<<e<<endl;}
  78. template<class T1,class T2> void debug(const T1& e1,const T2& e2){cout<<e1<<"\t"<<e2<<endl;}
  79. template<class T1,class T2,class T3> void debug(const T1& e1,const T2& e2,const T3& e3){cout<<e1<<"\t"<<e2<<"\t"<<e3<<endl;}
  80. template<class T1,class T2,class T3,class T4> void debug(const T1& e1,const T2& e2,const T3& e3,const T4& e4){cout<<e1<<"\t"<<e2<<"\t"<<e3<<"\t"<<e4<<endl;}
  81. template<class T1,class T2,class T3,class T4,class T5> void debug(const T1& e1,const T2& e2,const T3& e3,const T4& e4,const T5& e5){cout<<e1<<"\t"<<e2<<"\t"<<e3<<"\t"<<e4<<"\t"<<e5<<endl;}
  82. template<class T> void debug(vector<T>& e){int i;REP(i,SZ(e)) cout<<e[i]<<" ";cout<<endl;}
  83. template<class T> void debug(vector< basic_string<T> >& e){int i,j;REP(i,SZ(e)) {REP(j,SZ(e[i])) cout<<e[i][j];cout<<endl;} cout<<endl;}
  84. template<class T> void debug(vector< vector<T> >& e){int i,j;REP(i,SZ(e)) {REP(j,SZ(e[i])) cout<<e[i][j]<<"\t";cout<<endl;} cout<<endl;}
  85. template<class T> void debug(T e[SIZE][SIZE],int row,int col){int i,j;REP(i,row) {REP(j,col) cout<<e[i][j]<<" ";cout<<endl;}}
  86.  
  87. ll Pow(ll B,ll P){ ll R=1; while(P>0) {if(P%2==1) R=(R*B);P/=2;B=(B*B);}return R;} //compute b^p
  88. //struct pq{ int cost,node;bool operator<(const pq &b)const{return cost>b.cost;}};// Min Priority Queue
  89. //bool comp(pq a,pq b){ return a.cost > b.cost;} //Comp Sort
  90.  
  91. int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
  92. //int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
  93. //int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
  94.  
  95. vector<int>ans;
  96. int mat[SIZE][SIZE],row,col;
  97. vs grid;
  98.  
  99. void BFS(int x,int y)
  100. {
  101. //debug(x,y);
  102. int i,m,n;
  103. queue<pii>Q;
  104.  
  105. Q.push(MP(x,y));
  106. mat[x][y]=0;
  107. while(!Q.empty())
  108. {
  109. x=Q.front().first;
  110. y=Q.front().second;
  111. Q.pop();
  112.  
  113. REP(i,4)
  114. {
  115. m=x+dx[i];
  116. n=y+dy[i];
  117. if(m>=0 && m<row && n>=0 && n<col)
  118. {
  119. if(grid[m][n]!='#' && mat[m][n]==-1)
  120. {
  121. mat[m][n]=mat[x][y]+1;
  122. Q.push(MP(m,n));
  123. }
  124. }
  125. }
  126. }
  127. }
  128.  
  129. class Socialize
  130. {
  131. public:
  132. int average(vector <string> layout)
  133. {
  134. int i,j,sum,cnt,x,y,res;
  135. vector<pii>store;
  136.  
  137. grid=layout;
  138. row=SZ(layout);
  139. col=SZ(layout[0]);
  140. REP(i,row)
  141. {
  142. REP(j,col)
  143. {
  144. if(layout[i][j]=='P')
  145. {
  146. store.pb(MP(i,j));
  147. }
  148. }
  149. }
  150. sum=cnt=0;
  151. REP(i,SZ(store))
  152. {
  153. Clear(mat,-1);
  154. x=store[i].first;
  155. y=store[i].second;
  156. BFS(x,y);
  157. REP(j,SZ(store))
  158. {
  159. x=store[j].first;
  160. y=store[j].second;
  161. if(mat[x][y]>0)
  162. {
  163. cnt++;
  164. sum+=mat[x][y];
  165. }
  166. }
  167. }
  168. //debug(sum,cnt);
  169. if(cnt==0) return 0;
  170. res=(sum/(cnt+0.0)+0.5);
  171. return res;
  172. }
  173. };
  174.  
  175.  
  176. template<typename T> void print( T a ) {
  177. cerr << a;
  178. }
  179.  
  180. void print( long long a ) {
  181. cerr << a << "L";
  182. }
  183.  
  184. void print( string a ) {
  185. cerr << '"' << a << '"';
  186. }
  187.  
  188. template<typename T> void print( vector<T> a ) {
  189. cerr << "{";
  190. for ( int i = 0 ; i != a.size() ; i++ ) {
  191. if ( i != 0 ) cerr << ", ";
  192. print( a[i] );
  193. }
  194. cerr << "}" << endl;
  195. }
  196.  
  197. template<typename T> void assert_eq( int n, T have, T need ) {
  198. if ( have == need ) {
  199. cerr << "Case " << n << " passed." << endl;
  200. } else {
  201. cerr << "Case " << n << " failed: expected ";
  202. print( need );
  203. cerr << " received ";
  204. print( have );
  205. cerr << "." << endl;
  206. }
  207. }
  208.  
  209. template<typename T> void assert_eq( int n, vector<T> have, vector<T> need ) {
  210. if( have.size() != need.size() ) {
  211. cerr << "Case " << n << " failed: returned " << have.size() << " elements; expected " << need.size() << " elements.";
  212. print( have );
  213. print( need );
  214. return;
  215. }
  216. for( int i= 0; i < have.size(); i++ ) {
  217. if( have[i] != need[i] ) {
  218. cerr << "Case " << n << " failed. Expected and returned array differ in position " << i << ".";
  219. print( have );
  220. print( need );
  221. return;
  222. }
  223. }
  224. cerr << "Case " << n << " passed." << endl;
  225. }
  226. void assert_eq( int n, string have, string need ) {
  227. if ( have == need ) {
  228. cerr << "Case " << n << " passed." << endl;
  229. } else {
  230. cerr << "Case " << n << " failed: expected ";
  231. print( need );
  232. cerr << " received ";
  233. print( have );
  234. cerr << "." << endl;
  235. }
  236. }
  237.  
  238. int main( int argc, char* argv[] )
  239. {
  240.  
  241. Socialize objectSocialize;
  242.  
  243. //test case0
  244. vector <string> param00;
  245. param00.push_back("P");
  246. int ret0 = objectSocialize.average(param00);
  247. int need0 = 0;
  248. assert_eq(0,ret0,need0);
  249.  
  250. //test case1
  251. vector <string> param10;
  252. param10.push_back("#");
  253. int ret1 = objectSocialize.average(param10);
  254. int need1 = 0;
  255. assert_eq(1,ret1,need1);
  256.  
  257. //test case2
  258. vector <string> param20;
  259. param20.push_back("P#P");
  260. param20.push_back("P#.");
  261. param20.push_back("P#P");
  262. int ret2 = objectSocialize.average(param20);
  263. int need2 = 2;
  264. assert_eq(2,ret2,need2);
  265.  
  266. //test case3
  267. vector <string> param30;
  268. param30.push_back("P...P");
  269. param30.push_back("###..");
  270. param30.push_back("P...#");
  271. param30.push_back("####P");
  272. int ret3 = objectSocialize.average(param30);
  273. int need3 = 6;
  274. assert_eq(3,ret3,need3);
  275.  
  276. }
  277.