Submission #1569065

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int b[800][800];
char a[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(){



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))
{s.push(mp(x+1,y));
b[x+1][y]=f;
}

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

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







}}
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);
          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();
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