Submission #1569166


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int b[800][800];
char a[800][803];
int flag[800][803];
int h,w;
#define fi first
#define  se second
#define pe pair<int,int>
int ans;
queue<pair<int,int> > s;
#define mp make_pair
void dfs(int k){



while(!s.empty()){
        pe xx=s.front();
        s.pop();

        int x=xx.fi;
        int y=xx.se;

if(x==(h-1)||y==(w-1)||(x==0)||(y==0)){
        ans=min(ans,b[x][y]);

continue;

}
int f=b[x][y]+1;
int x1=f,x2=f,x3=f,x4=f;
if(a[x+1][y]=='#'&&flag[x][y]==0&&(f-1)<=k){

    x1=f+k;
    flag[x+1][y]=1;

}
if(a[x][y+1]=='#'&&flag[x][y]==0&&(f-1)<=k){

    x2=f+k;
    flag[x][y+1]=1;

}
if(a[x-1][y]=='#'&&flag[x][y]==0&&(f-1)<=k){

    x3=f+k;
    flag[x-1][y]=1;

}
if(a[x][y-1]=='#'&&flag[x][y]==0&&(f-1)<=k){

    x4=f+k;
    flag[x][y-1]=1;

}
if(b[x+1][y]>(x1))
{s.push(mp(x+1,y));
b[x+1][y]=x1;
if(flag[x][y])
flag[x+1][y]=flag[x][y];

}

if(b[x][y+1]>(x2)){
s.push(mp(x,y+1));
b[x][y+1]=x2;
if(flag[x][y])
flag[x][y+1]=flag[x][y];
}


if(b[x-1][y]>(x3)){
s.push(mp(x-1,y));
b[x-1][y]=f;
if(flag[x][y])
flag[x-1][y]=flag[x][y];

}
if(b[x][y-1]>(x4)){
s.push(mp(x,y-1));

b[x][y-1]=f;
if(flag[x][y])
flag[x][y-1]=flag[x][y];
}
}







}
void dfs1(){



while(!s.empty()){
        pe xx=s.front();
        s.pop();

        int x=xx.fi;
        int y=xx.se;

if(x==(h-1)||y==(w-1)||(x==0)||(y==0)){
        ans=min(ans,b[x][y]);

continue;

}
int f=b[x][y]+1;
if(b[x+1][y]>(f)&&a[x+1][y]!='#')
{s.push(mp(x+1,y));
b[x+1][y]=f;
}

if(b[x][y+1]>(f)&&(a[x][y+1]!='#')){
s.push(mp(x,y+1));
b[x][y+1]=f;

}
if(b[x-1][y]>(f)&&(a[x-1][y]!='#')){
s.push(mp(x-1,y));
b[x-1][y]=f;
}
if(b[x][y-1]>(f)&&(a[x][y-1]!='#')){
s.push(mp(x,y-1));
b[x][y-1]=f;
}







}}



int solve(int mid,int x,int y,int k){
    int i,j;
 for(i=0;i<h;i++)
        for(j=0;j<w;j++)
          b[i][j]=(1e6);
          for(i=0;i<h;i++)
        for(j=0;j<w;j++)
          flag[i][j]=0;
          b[x][y]=0;
ans=1e6;
int zz=s.size();
for(i=0;i<zz;i++)
    s.pop();
s.push(mp(x,y));
if(mid==1){

    dfs1();
if(ans<=k)
    return 1;
else
    return 0;

}
else{


    dfs(k);
int ff=mid*k;
if(ans<=ff)
    return 1;
else
    return 0;


}

}

int main(){

int i,j;

int k;
cin>>h>>w>>k;
int x,y;
int se=1;
for(i=0;i<h;i++){
    cin>>a[i];
    for(j=0;j<w;j++){

        if(a[i][j]=='S'){

            x=i;
            y=j;
        }

    }

    }

    int l=1;
    int h1=100000;
int mid;

    while(l<=(h1)){

         mid=(l+h1)/2;




        int an=solve(mid,x,y,k);


     if(an){


        se=mid;

        h1=mid-1;

     }
     else{

        l=mid+1;




     }





    }
    cout<<se<<endl;

return 0;
}

Submission Info

Submission Time
Task C - Closed Rooms
User adam1007
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2876 Byte
Status WA
Exec Time 546 ms
Memory 6016 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 3
AC × 29
WA × 17
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in4.txt, in40.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
in1.txt AC 322 ms 5888 KB
in10.txt AC 332 ms 5888 KB
in11.txt WA 546 ms 5888 KB
in12.txt WA 342 ms 5888 KB
in13.txt WA 489 ms 5888 KB
in14.txt WA 324 ms 5888 KB
in15.txt WA 413 ms 5888 KB
in16.txt WA 382 ms 5888 KB
in17.txt WA 316 ms 5888 KB
in18.txt WA 474 ms 5888 KB
in19.txt WA 542 ms 5888 KB
in2.txt AC 523 ms 5888 KB
in20.txt AC 4 ms 5888 KB
in21.txt AC 2 ms 2304 KB
in22.txt AC 2 ms 2304 KB
in23.txt AC 314 ms 5888 KB
in24.txt WA 378 ms 5888 KB
in25.txt WA 332 ms 5888 KB
in26.txt AC 394 ms 5888 KB
in27.txt AC 319 ms 6016 KB
in28.txt AC 348 ms 5888 KB
in29.txt AC 346 ms 5888 KB
in3.txt AC 349 ms 5888 KB
in30.txt AC 356 ms 5888 KB
in31.txt AC 298 ms 5888 KB
in32.txt AC 313 ms 5888 KB
in33.txt WA 265 ms 5888 KB
in34.txt WA 250 ms 5888 KB
in35.txt AC 242 ms 5888 KB
in36.txt WA 310 ms 5888 KB
in37.txt WA 263 ms 5888 KB
in38.txt AC 312 ms 5888 KB
in39.txt AC 261 ms 5888 KB
in4.txt WA 346 ms 5888 KB
in40.txt AC 250 ms 5888 KB
in5.txt WA 366 ms 5888 KB
in6.txt AC 361 ms 5888 KB
in7.txt AC 327 ms 5888 KB
in8.txt AC 472 ms 5888 KB
in9.txt AC 318 ms 5888 KB
sample1.txt AC 2 ms 2304 KB
sample2.txt AC 2 ms 2304 KB
sample3.txt AC 2 ms 2304 KB