| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 297327 | 2020-09-11T13:48:47 Z | kshitij_sodani | Vision Program (IOI19_vision) | C++14 | 0 ms | 0 KB |
//nowruz backup
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
int it[1100][1100];
char ans[1100][1100];
int deg[1100][1100];
mt19937 rng;
vector<int> x={1,-1,0,0};
vector<int> y={0,0,1,-1};
int n,m,k;
void push(pair<int,int> no){
for(int i=0;i<4;i++){
int xo=x[i]+no.a;
int yy=y[i]+no.b;
if(xo<0 or yy<0 or xo>=n or yy>=m){
continue;
}
if(it[xo][yy]==0){
continue;
}
deg[xo][yy]+=1;
}
}
int cur;
void solve(){
rng=mt19937(chrono::steady_clock::now().time_since_epoch().count());
cin>>n>>m>>k;
vector<pair<int,int>> xx;
pair<int,int> st={-1,-1};
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
char s;
cin>>s;
if(s=='#'){
it[i][j]=0;
}
else{
it[i][j]=1;
xx.pb({i,j});
/* if(cur==9 and st.a!=-1){
continue;
}*/
st={i,j};
}
}
}
int ma=-1;
for(int ii=0;ii<10;ii++){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
deg[i][j]=0;
}
}
shuffle(xx.begin(),xx.end(),rng);
//if(cur==9){
st=xx[0];
//}
//=xx[0];
queue<pair<int,int>> ss;
ss.push(st);
push(st);
vector<pair<int,int>> tt;
tt.pb(st);
while(ss.size()){
pair<int,int> no=ss.front();
ss.pop();
tt.pb(no);
vector<int> st={0,1,2,3};
//shuffle(st.begin(),st.end(),rng);
for(auto i:st){
int xo=x[i]+no.a;
int yy=y[i]+no.b;
if(xo<0 or yy<0 or xo>=n or yy>=m){
continue;
}
if(it[xo][yy]==0){
continue;
}
if(deg[xo][yy]==1){
push({xo,yy});
ss.push({xo,yy});
}
}
}
//continue;
int co=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(deg[i][j]==1){
co+=1;
}
}
}
if(co>ma){
ma=co;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(it[i][j]==0){
ans[i][j]='#';
}
else{
ans[i][j]='X';
}
}
}
//cout<<tt.size()<<endl;
for(auto i:tt){
ans[i.a][i.b]='.';
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<ans[i][j];
}
cout<<endl;
}
/* for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i==m-1){
cout<<".";
continue;
}
if(j==m-1){
cout<<"X";
continue;
}
if(j%3==1){
cout<<".";
continue;
}
else{
if((j/3)%2==0){
if(i<m-3 and i%2==0){
cout<<".";
continue;
}
}
else{
if(i<m-3 and i%2==1){
cout<<".";
continue;
}
}
}
cout<<"X";
continue;
if(j%4==1){
cout<<".";
continue;
}
else if(j%4==0 or j%4==2){
if((m-i)%2==1){
cout<<".";
continue;
}
}
else{
if(i==m-1 or i==m-2){
cout<<".";
continue;
}
}
// else{
cout<<"X";
// }
}
cout<<endl;
}
*/
}
int main(){
for(int i=1;i<=10;i++){
if( i==2 or i==4){
continue;
}
cur=i;
freopen(("nowruz"+to_string(i)+".in.txt").c_str(),"r",stdin);
freopen(("nowruz"+to_string(i)+".out"+".txt").c_str(),"w",stdout);
solve();
}
return 0;
}