Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define x first
- #define y second
- #define pii pair<int,int>
- #define pb push_back
- using namespace std;
- typedef long long int ll;
- typedef unsigned long long int ull;
- const char en='\n';
- const int MOD=1000000007;
- const int N=1050;
- int n,m,k,z,sa,sc;
- string h[N];
- string res[N],ree[N];
- bool bio[N][N];
- bool bio1[N][N],bio2[N][N];
- vector<int> dx={0,1,0,-1};
- vector<int> dy={1,0,-1,0};
- vector<int> x,y;
- bool ok(int i,int j)
- {
- return (i>=0 && j>=0 && i<n && j<m && !bio[i][j] && h[i][j]=='.');
- }
- void bfs(int i,int j,int i1,int j1)
- {
- queue<pair<pii,pii>> q;
- q.push({{i,j},{i1,j1}});
- while (q.size())
- {
- int i=q.front().x.x,j=q.front().x.y,i1=q.front().y.x,j1=q.front().y.y;
- q.pop();
- if (!ok(i,j)) continue;
- //if (rand()%30==0) cout<<"a "<<i<<' '<<j<<en;
- bio[i][j]=1;
- bio1[i][j]=1;
- int st=z,e=z+4;
- z+=4;
- z%=x.size();
- if (rand()%100000<sa)
- {
- //cout<<"ra "<<i<<' '<<j<<endl;
- for (int o=st;o<e;++o) bio[i+x[o]][j+y[o]]=1;
- }
- bool go=1;
- 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]])
- {
- bio1[i][j]=0;
- /*cout<<i<<' '<<j<<' '<<i+x[o]<<' '<<j+y[o]<<' '<<i1<<' '<<j1<<endl;
- for (int i=0;i<n;++i) for (int j=0;j<m;++j)
- {
- if (bio1[i][j]) ree[i][j]='.';
- else if (h[i][j]=='#') ree[i][j]='#';
- else ree[i][j]='X';
- }
- for (int q=0;q<=min(i+1,n-1);++q,cout<<en) for (int w=0;w<=min(j+1,m-1);++w)
- {
- cout<<ree[q][w];
- }*/
- go=0;
- break;
- }
- if (!go) continue;
- for (int o=st;o<e;++o)
- {
- if (ok(i+x[o],j+y[o]))
- {
- q.push({{i+x[o],j+y[o]},{i,j}});
- }
- else
- {
- /*cout<<i<<' '<<j<<' '<<i+x[o]<<' '<<j+y[o]<<' '<<i1<<' '<<j1<<endl;
- for (int i=0;i<n;++i) for (int j=0;j<m;++j)
- {
- if (bio1[i][j]) ree[i][j]='.';
- else if (h[i][j]=='#') ree[i][j]='#';
- else ree[i][j]='X';
- }
- for (int q=0;q<=min(i+1,n-1);++q,cout<<en) for (int w=0;w<=min(j+1,m-1);++w)
- {
- cout<<ree[q][w];
- }*/
- }
- }
- }
- }
- void dfs2(int i,int j,int i2,int j2)
- {
- if (!(i>=0 && j>=0 && i<n && j<m)) return;
- int rr=0;
- for (int r=0;r<4;++r)
- {
- int i1=i+dx[r],j1=j+dy[r];
- if (!(i1>=0 && j1>=0 && i1<n && j1<m)) ++rr;
- else if (!bio1[i1][j1]) ++rr;
- }
- if (rr==3 && h[i][j]!='#') bio1[i][j]=1;
- if (!bio1[i][j]) return;
- if (sc<0) return;
- //cout<<"b "<<i<<' '<<j<<endl;
- bio2[i][j]=1;
- int st=z;
- for (int r=0;r<4;++r)
- {
- int i1=i+x[r+st],j1=j+y[r+st];
- if (i1!=i2 || j1!=j2)
- {
- if (i1>=0 && j1>=0 && bio2[i1][j1])
- {
- sc=-MOD;
- //cout<<i<<' '<<j<<' '<<i1<<' '<<j1<<' '<<i2<<' '<<j2<<endl;
- return;
- }
- else dfs2(i1,j1,i,j);
- }
- }
- z=(z+4)%x.size();
- rr=0;
- for (int r=0;r<4;++r)
- {
- int i1=i+dx[r],j1=j+dy[r];
- if (!(i1>=0 && j1>=0 && i1<n && j1<m)) ++rr;
- else if (!bio1[i1][j1]) ++rr;
- }
- if (rr==3) ++sc;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- for (int qqqqqq=0;qqqqqq<10;++qqqqqq)
- {
- string eee=to_string(qqqqqq);
- string aaa="input_00"+eee+".txt",bbb="output_00"+eee+".txt";
- freopen(aaa.c_str(),"r",stdin);
- ofstream fout(bbb);
- cin>>n>>m>>k;
- sa=100000/pow(n*m,100);
- for (int i=0;i<n;++i) cin>>h[i],res[i]=h[i],ree[i]=h[i];
- int cl=clock();
- int ma=-MOD;
- while (clock()-cl<=8*CLOCKS_PER_SEC)
- {
- x.clear();
- y.clear();
- z=0;
- memset(bio,0,sizeof(bio));
- memset(bio1,0,sizeof(bio1));
- memset(bio2,0,sizeof(bio2));
- sc=0;
- //cout<<"memset done."<<endl;
- for (int i=0;i<n*m;++i)
- {
- vector<int> c={0,1,2,3};
- random_shuffle(c.begin(),c.end());
- for (int j: c) x.pb(dx[j]),y.pb(dy[j]);
- }
- //cout<<"vectors done."<<endl;
- int si=rand()%n,sj=rand()%m;
- while (h[si][sj]=='#')
- {
- si=rand()%n,sj=rand()%m;
- }
- bfs(si,sj,-1,-1);
- dfs2(si,sj,-1,-1);
- //cout<<"both dfs complete."<<endl;
- if (sc>ma)
- {
- for (int i=0;i<n;++i) for (int j=0;j<m;++j)
- {
- if (bio1[i][j]) res[i][j]='.';
- else if (h[i][j]=='#') res[i][j]='#';
- else res[i][j]='X';
- }
- ma=sc;
- }
- /*if (qqqqqq==1 || qqqqqq==3)
- {
- for (int i=0;i<n;++i) for (int j=0;j<m;++j) res[i][j]='.';
- for (int j=0;j<m;++j) if (j%2==0) res[1][j]='X';
- for (int i=3;i<n;i+=2) for (int j=0;j<m;++j) if (j%4!=1) res[i][j]='X';
- for (int i=2;i<n;i+=2) for (int j=0;j<m;++j) if (j%4==3) res[i][j]='X';
- }*/
- }
- cout<<k<<' '<<ma<<endl;
- for (int i=0;i<n;++i,fout<<endl) for (int j=0;j<m;++j) fout<<res[i][j];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement