Submission #1208555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208555		timeflew	Mecho (IOI09_mecho)	C++20	5 / 100	135 ms	4580 KiB

mecho

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(), x.end()

const int mxN=8e2;

char c[mxN][mxN];
int vis[mxN][mxN];
bool vis1[mxN][mxN];
pair<int, int> st, ed;
int n, s;
int dx[4]={0, 0, 1, -1};
int dy[4]={1, -1, 0, 0};

bool valid(int x, int y) {
  return (x>=0&&x<n&&y>=0&&y<n&&c[x][y]!='T');
}

bool check(int x) {
  queue<array<int, 4>> q;//x y step state_s
  q.push({st.ff, st.ss, x+1, 0});
  memset(vis1, 0, sizeof(vis1));
  vis1[st.ff][st.ss]=1;
  while(q.size()) {
      auto [xx, yy, step, state]=q.front();
      if(ed.ff==xx&&ed.ss==yy) return 1;
      q.pop();
      for(int i=0; i<4; i++) {
          int nx=xx+dx[i], ny=yy+dy[i];
          if(valid(nx, ny)&&vis[nx][ny]>step&&!vis1[nx][ny]) {
              state++;
              vis1[nx][ny]=1;
              if(state==s) {
                  // if(step+1==vis[nx][ny]) continue;
                  q.push({nx, ny, step+1, 1});
              } else {
                  q.push({nx, ny, step, state+1});
              }
          }
      } 
  }
  return 0;
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin>>n>>s;
  queue<array<int, 3>> q;
  memset(vis, 0x3f, sizeof(vis));
  for(int i=0; i<n; i++) {
      for(int j=0; j<n; j++) {
          cin>>c[i][j];// t g m d h
          if(c[i][j]=='M') st={i, j};
          if(c[i][j]=='D') ed={i, j};
          if(c[i][j]=='H') q.push({i, j, 0}), vis[i][j]=0;
      }
  }
  while(q.size()) {
      auto [x, y, now]=q.front();
      q.pop();
      for(int i=0; i<4; i++) {
          int nx=x+dx[i], ny=y+dy[i];
          if(vis[nx][ny]==0x3f3f3f3f&&valid(nx, ny)) {
              vis[nx][ny]=now+1;
              q.push({nx, ny, now+1});
          }
      }
  }
  int l=0, r=s, ans=-1;
  while(l<=r) {
      int mid=(l+r)/2;
      if(check(mid)) {
          ans=mid;
          l=mid+1;
      } else {
          r=mid-1;
      }
  }
  cout<<ans<<"\n";
  return 0;
}

• Subtask 1: 5 / 100