Submission #1569162

---

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]=(1e6);
          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

Judge Result