Submission #1569167


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]=x3;
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]=x4;
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 2878 Byte
Status WA
Exec Time 629 ms
Memory 5888 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 3
AC × 34
WA × 12
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 586 ms 5888 KB
in10.txt AC 439 ms 5888 KB
in11.txt WA 629 ms 5888 KB
in12.txt WA 608 ms 5888 KB
in13.txt AC 355 ms 5888 KB
in14.txt WA 470 ms 5888 KB
in15.txt AC 326 ms 5888 KB
in16.txt AC 629 ms 5888 KB
in17.txt WA 366 ms 5888 KB
in18.txt WA 537 ms 5888 KB
in19.txt WA 534 ms 5888 KB
in2.txt AC 542 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 308 ms 5888 KB
in24.txt WA 557 ms 5888 KB
in25.txt AC 463 ms 5888 KB
in26.txt AC 440 ms 5888 KB
in27.txt AC 327 ms 5888 KB
in28.txt AC 363 ms 5888 KB
in29.txt AC 369 ms 5888 KB
in3.txt AC 387 ms 5888 KB
in30.txt AC 378 ms 5888 KB
in31.txt AC 295 ms 5888 KB
in32.txt AC 307 ms 5888 KB
in33.txt WA 249 ms 5888 KB
in34.txt WA 251 ms 5888 KB
in35.txt AC 246 ms 5888 KB
in36.txt WA 270 ms 5888 KB
in37.txt AC 260 ms 5888 KB
in38.txt AC 285 ms 5888 KB
in39.txt AC 265 ms 5888 KB
in4.txt WA 487 ms 5888 KB
in40.txt AC 256 ms 5888 KB
in5.txt WA 482 ms 5888 KB
in6.txt AC 333 ms 5888 KB
in7.txt AC 314 ms 5888 KB
in8.txt AC 342 ms 5888 KB
in9.txt AC 313 ms 5888 KB
sample1.txt AC 2 ms 2304 KB
sample2.txt AC 2 ms 2304 KB
sample3.txt AC 2 ms 2304 KB