Advertisement
Guest User

Untitled

a guest
Jun 25th, 2019
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.31 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define x first
  3. #define y second
  4. #define pii pair<int,int>
  5. #define pb push_back
  6.  
  7. using namespace std;
  8.  
  9. typedef long long int ll;
  10. typedef unsigned long long int ull;
  11. const char en='\n';
  12. const int MOD=1000000007;
  13.  
  14. const int N=1050;
  15. int n,m,k,z,sa,sc;
  16. string h[N];
  17. string res[N],ree[N];
  18. bool bio[N][N];
  19. bool bio1[N][N],bio2[N][N];
  20. vector<int> dx={0,1,0,-1};
  21. vector<int> dy={1,0,-1,0};
  22. vector<int> x,y;
  23.  
  24. bool ok(int i,int j)
  25. {
  26. return (i>=0 && j>=0 && i<n && j<m && !bio[i][j] && h[i][j]=='.');
  27. }
  28.  
  29. void bfs(int i,int j,int i1,int j1)
  30. {
  31. queue<pair<pii,pii>> q;
  32. q.push({{i,j},{i1,j1}});
  33. while (q.size())
  34. {
  35. int i=q.front().x.x,j=q.front().x.y,i1=q.front().y.x,j1=q.front().y.y;
  36. q.pop();
  37. if (!ok(i,j)) continue;
  38. //if (rand()%30==0) cout<<"a "<<i<<' '<<j<<en;
  39. bio[i][j]=1;
  40. bio1[i][j]=1;
  41. int st=z,e=z+4;
  42. z+=4;
  43. z%=x.size();
  44. if (rand()%100000<sa)
  45. {
  46. //cout<<"ra "<<i<<' '<<j<<endl;
  47. for (int o=st;o<e;++o) bio[i+x[o]][j+y[o]]=1;
  48. }
  49. bool go=1;
  50. for (int o=st;o<e;++o) if (!ok(i+x[o],j+y[o]) && i+x[o]>=0 && j+y[o]>=0 && (i+x[o]!=i1 || j+y[o]!=j1) && bio1[i+x[o]][j+y[o]])
  51. {
  52. bio1[i][j]=0;
  53. /*cout<<i<<' '<<j<<' '<<i+x[o]<<' '<<j+y[o]<<' '<<i1<<' '<<j1<<endl;
  54. for (int i=0;i<n;++i) for (int j=0;j<m;++j)
  55. {
  56. if (bio1[i][j]) ree[i][j]='.';
  57. else if (h[i][j]=='#') ree[i][j]='#';
  58. else ree[i][j]='X';
  59. }
  60. for (int q=0;q<=min(i+1,n-1);++q,cout<<en) for (int w=0;w<=min(j+1,m-1);++w)
  61. {
  62. cout<<ree[q][w];
  63. }*/
  64. go=0;
  65. break;
  66. }
  67. if (!go) continue;
  68. for (int o=st;o<e;++o)
  69. {
  70. if (ok(i+x[o],j+y[o]))
  71. {
  72. q.push({{i+x[o],j+y[o]},{i,j}});
  73. }
  74. else
  75. {
  76. /*cout<<i<<' '<<j<<' '<<i+x[o]<<' '<<j+y[o]<<' '<<i1<<' '<<j1<<endl;
  77. for (int i=0;i<n;++i) for (int j=0;j<m;++j)
  78. {
  79. if (bio1[i][j]) ree[i][j]='.';
  80. else if (h[i][j]=='#') ree[i][j]='#';
  81. else ree[i][j]='X';
  82. }
  83. for (int q=0;q<=min(i+1,n-1);++q,cout<<en) for (int w=0;w<=min(j+1,m-1);++w)
  84. {
  85. cout<<ree[q][w];
  86. }*/
  87. }
  88. }
  89. }
  90. }
  91.  
  92. void dfs2(int i,int j,int i2,int j2)
  93. {
  94. if (!(i>=0 && j>=0 && i<n && j<m)) return;
  95. int rr=0;
  96. for (int r=0;r<4;++r)
  97. {
  98. int i1=i+dx[r],j1=j+dy[r];
  99. if (!(i1>=0 && j1>=0 && i1<n && j1<m)) ++rr;
  100. else if (!bio1[i1][j1]) ++rr;
  101. }
  102. if (rr==3 && h[i][j]!='#') bio1[i][j]=1;
  103. if (!bio1[i][j]) return;
  104. if (sc<0) return;
  105. //cout<<"b "<<i<<' '<<j<<endl;
  106. bio2[i][j]=1;
  107. int st=z;
  108. for (int r=0;r<4;++r)
  109. {
  110. int i1=i+x[r+st],j1=j+y[r+st];
  111. if (i1!=i2 || j1!=j2)
  112. {
  113. if (i1>=0 && j1>=0 && bio2[i1][j1])
  114. {
  115. sc=-MOD;
  116. //cout<<i<<' '<<j<<' '<<i1<<' '<<j1<<' '<<i2<<' '<<j2<<endl;
  117. return;
  118. }
  119. else dfs2(i1,j1,i,j);
  120. }
  121. }
  122. z=(z+4)%x.size();
  123. rr=0;
  124. for (int r=0;r<4;++r)
  125. {
  126. int i1=i+dx[r],j1=j+dy[r];
  127. if (!(i1>=0 && j1>=0 && i1<n && j1<m)) ++rr;
  128. else if (!bio1[i1][j1]) ++rr;
  129. }
  130. if (rr==3) ++sc;
  131. }
  132.  
  133. int main()
  134. {
  135. ios_base::sync_with_stdio(false);
  136. cin.tie(0);
  137. for (int qqqqqq=0;qqqqqq<10;++qqqqqq)
  138. {
  139. string eee=to_string(qqqqqq);
  140. string aaa="input_00"+eee+".txt",bbb="output_00"+eee+".txt";
  141. freopen(aaa.c_str(),"r",stdin);
  142. ofstream fout(bbb);
  143. cin>>n>>m>>k;
  144. sa=100000/pow(n*m,100);
  145. for (int i=0;i<n;++i) cin>>h[i],res[i]=h[i],ree[i]=h[i];
  146. int cl=clock();
  147. int ma=-MOD;
  148. while (clock()-cl<=8*CLOCKS_PER_SEC)
  149. {
  150. x.clear();
  151. y.clear();
  152. z=0;
  153. memset(bio,0,sizeof(bio));
  154. memset(bio1,0,sizeof(bio1));
  155. memset(bio2,0,sizeof(bio2));
  156. sc=0;
  157. //cout<<"memset done."<<endl;
  158. for (int i=0;i<n*m;++i)
  159. {
  160. vector<int> c={0,1,2,3};
  161. random_shuffle(c.begin(),c.end());
  162. for (int j: c) x.pb(dx[j]),y.pb(dy[j]);
  163. }
  164. //cout<<"vectors done."<<endl;
  165. int si=rand()%n,sj=rand()%m;
  166. while (h[si][sj]=='#')
  167. {
  168. si=rand()%n,sj=rand()%m;
  169. }
  170. bfs(si,sj,-1,-1);
  171. dfs2(si,sj,-1,-1);
  172. //cout<<"both dfs complete."<<endl;
  173. if (sc>ma)
  174. {
  175. for (int i=0;i<n;++i) for (int j=0;j<m;++j)
  176. {
  177. if (bio1[i][j]) res[i][j]='.';
  178. else if (h[i][j]=='#') res[i][j]='#';
  179. else res[i][j]='X';
  180. }
  181. ma=sc;
  182. }
  183. /*if (qqqqqq==1 || qqqqqq==3)
  184. {
  185. for (int i=0;i<n;++i) for (int j=0;j<m;++j) res[i][j]='.';
  186. for (int j=0;j<m;++j) if (j%2==0) res[1][j]='X';
  187. for (int i=3;i<n;i+=2) for (int j=0;j<m;++j) if (j%4!=1) res[i][j]='X';
  188. for (int i=2;i<n;i+=2) for (int j=0;j<m;++j) if (j%4==3) res[i][j]='X';
  189. }*/
  190. }
  191. cout<<k<<' '<<ma<<endl;
  192. for (int i=0;i<n;++i,fout<<endl) for (int j=0;j<m;++j) fout<<res[i][j];
  193. }
  194. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement