제출 #583986

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
583986		Omar_Elgedawy	Mecho (IOI09_mecho)	C++14	84 / 100	166 ms	5708 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define cin(vec)        for(auto& i : vec) cin >> i
#define cout(vec)       for(auto& i : vec) cout << i << " "; cout << "\n";
#define fast            ios::sync_with_stdio(0);cin.tie(0);
#define loop(i,a,b)     for (int i = a; i < b; i++)
#define F               first
#define S               second
#define pb(n)           push_back(n)
#define pf(n)           push_front(n)
#define dci(d)          fixed<<setprecision(d)
#define sp              ' '
#define el              '\n'
#define all(v)          v.begin(),v.end()
// #define int             long long
int dx[8]= {0,0,1,-1,-1,1,1,-1};
int dy[8]= {-1,1,0,0,-1,1,-1,1};
int const N=8e2+5,M=1e2+5,Mod=1e9;
char grid[N][N];
int block[N][N],n,s;
bool vis[N][N];
int valid(int i,int j){
  return (i>=0&&j>=0&&i<n&&j<n);
}
struct cell{
  int i;
  int j;
  int t;
};
queue<cell>q;
void bfs(){
  while(q.size()){
    int i=q.front().i;
    int j=q.front().j;
    int t=q.front().t;
    q.pop();
    if(block[i][j]<=t){
      continue;
    }
    block[i][j]=t;
    for(int k=0;k<4;k++){
      int x=dx[k]+i;
      int y=dy[k]+j;
      if(valid(x,y)&&(grid[x][y]=='G'||grid[x][y]=='M')&&!vis[x][y]){
        q.push({x,y,t+1});
      }
    }
  }
}
bool bfs2(int i,int j,int st){
  while(q.size())q.pop();
  q.push({i,j,0});
  vis[i][j]=1;
  int t;
  while(q.size()){
    i=q.front().i;
    j=q.front().j;
    t=q.front().t;
    q.pop();
    if(grid[i][j]=='D')return 1;
    for(int k=0;k<4;k++){
      int x=dx[k]+i;
      int y=dy[k]+j;
      if(valid(x,y)&&(grid[x][y]=='G'||grid[x][y]=='D')&&block[x][y]>st+(t+1)/s&&!vis[x][y]){
        q.push({x,y,t+1});
        vis[x][y]=1;
      }
    }
  }
  return 0;
}
void testcase(int h){
  cin>>n>>s;
  int xst,yst,xed,yed;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      block[i][j]=1e9;
    }
  }
  for(int i=0;i<n;i++){
    string s;cin>>s;
    for(int j=0;j<n;j++){
      grid[i][j]=s[j];
      if(s[j]=='T')
        block[i][j]=-1;
      if(s[j]=='H')
        q.push({i,j,0});
      if(s[j]=='M')xst=i,yst=j;
      if(s[j]=='D')xed=i,yed=j;
    }
  }
  bfs();
  // for(int i=0;i<n;i++){
  //   for(int j=0;j<n;j++){
  //     cout<<block[i][j]<<' ';
  //   }cout<<el;
  // }
  int l=0,r=n*n*n;
  int mx=-1;
  while(l<=r){
    int m=(l+r)/2;
    // cout<<l<<' '<<m<<' '<<r<<el;
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        vis[i][j]=0;
    int x=bfs2(xst,yst,m);
    if(x){
      mx=m;
      l=m+1;
    }
    else{
      r=m-1;
    }
  }
  cout<<mx<<el;
}
int32_t main()
{
  // fast
  testcase(1);
  // int tc;cin>>tc;for(int i=1;i<=tc;i++)testcase(i);
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

mecho.cpp: In function 'void testcase(int)':
mecho.cpp:74:15: warning: variable 'xed' set but not used [-Wunused-but-set-variable]
   74 |   int xst,yst,xed,yed;
      |               ^~~
mecho.cpp:74:19: warning: variable 'yed' set but not used [-Wunused-but-set-variable]
   74 |   int xst,yst,xed,yed;
      |                   ^~~
mecho.cpp:106:15: warning: 'yst' may be used uninitialized in this function [-Wmaybe-uninitialized]
  106 |     int x=bfs2(xst,yst,m);
      |           ~~~~^~~~~~~~~~~
mecho.cpp:106:15: warning: 'xst' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 84 / 100