Submission #1169361

#TimeUsernameProblemLanguageResultExecution timeMemory
1169361I_FloPPed21Mecho (IOI09_mecho)C++20
4 / 100
406 ms131072 KiB
#include <iostream> #include <queue> using namespace std; const int N=805; int n,m; char mat[N][N]; int dx[]= {1,0,-1,0}; int dy[]= {0,-1,0,1}; bool inmat(int i,int j) { return(i>=1&&i<=n&&j>=1&&j<=n); } struct mecho { int x,y,val,rem; }; bool viz[N][N]; int timp[N][N]; void citeste() { cin>>n>>m; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) cin>>mat[i][j]; } } queue<mecho>q; void do_bees() { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { timp[i][j]=1e9+3; if(mat[i][j]=='H') { timp[i][j]=0; viz[i][j]=true; q.push({i,j}); } } } while(!q.empty()) { int x=q.front().x; int y=q.front().y; q.pop(); for(int i=0; i<4; i++) { int a=x+dx[i]; int b=y+dy[i]; if(!inmat(a,b)) continue; if(mat[a][b]=='T'||mat[a][b]=='D') continue; if(viz[a][b]==false||timp[a][b]>timp[x][y]) { viz[a][b]=true; timp[a][b]=timp[x][y]+1; q.push({a,b,0,0}); } } } } int ans=-1; bool check(int val) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { viz[i][j]=false; if(mat[i][j]=='M') { viz[i][j]=true; q.push({i,j,val,m-1}); } } } while(!q.empty()) { int x=q.front().x; int y=q.front().y; int val=q.front().val; if(timp[x][y]<=val) { viz[x][y]=false; break; } int cate=q.front().rem; if(cate==0) { val++; cate=m; } cate--; q.pop(); for(int i=0; i<4; i++) { int a=x+dx[i]; int b=y+dy[i]; if(!inmat(a,b)) continue; if(mat[a][b]=='T') continue; if(timp[a][b]>val&&viz[a][b]==false) { viz[a][b]=true; q.push({a,b,val,cate}); } } } for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(mat[i][j]=='D') if(viz[i][j]==true) return true; return false; } void bin_search() { int st=0,dr=n*n; while(st<=dr) { int mij=(st+dr)/2; if(check(mij)) { ans=mij; st=mij+1; } else { dr=mij-1; } } cout<<ans; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); citeste(); do_bees(); bin_search(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...