Submission #1180954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180954		nolqf	Mecho (IOI09_mecho)	C++20	95 / 100	143 ms	4424 KiB

mecho

#include <iostream>
#include <queue>

using namespace std;

const int MAXN = 8e2;
const int INF = 2e9;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

string T[1 + MAXN];
int lim[1 + MAXN][1 + MAXN];
bool viz[1 + MAXN][1 + MAXN];
int n, s, xs, ys, xd, yd;

bool out( int x, int y ) {
  return 1 > x || 1 > y || n < x || n < y;
}

struct State {
  int x, y;
  int now, cnt;
};

bool check( int tt ) {
  for ( int i = 1; i <= n; ++i ) {
    for ( int j = 1; j <= n; ++j ) {
      viz[i][j] = false;
    }
  }
  queue<State> q;
  q.push({xs, ys, 0, 0});
  viz[xs][ys] = true;
  while ( !q.empty() ) {
    auto [x, y, now, cnt] = q.front();
    q.pop();
    int nnow = now + 1, ncnt = cnt;
    if ( nnow == s ) {
      nnow = 0;
      ++ncnt;
    }
    for ( int d = 0; d < 4; ++d ) {
      int nx = x + dx[d], ny = y + dy[d];
      if ( !out(nx, ny) && !viz[nx][ny] ) {
        if ( nx == xd && ny == yd ) {
          return true;
        }
        if ( lim[nx][ny] > tt + ncnt ) {
          q.push({nx, ny, nnow, ncnt});
          viz[nx][ny] = true;
        }
      }
    }
  }
  return false;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> s;
  queue<pair<int, int>> q;
  for ( int i = 1; i <= n; ++i ) {
    cin >> T[i];
    T[i] = '#' + T[i];
    for ( int j = 1; j <= n; ++j ) {
      lim[i][j] = INF;
      if ( T[i][j] == 'H' ) {
        q.push({i, j});
        lim[i][j] = 0;
      } else if ( T[i][j] == 'T' ) {
        lim[i][j] = 0;	       
      } else if ( T[i][j] == 'M' ) {
        xs = i, ys = j;
      } else if ( T[i][j] == 'D' ) {
        xd = i, yd = j;
      }
    }
  }
  while ( !q.empty() ) {
    auto [i, j] = q.front();
    q.pop();
    for ( int d = 0; d < 4; ++d ) {
      int ni = i + dx[d], nj = j + dy[d];
      if ( !out(ni, nj) && lim[ni][nj] == INF ) {
        lim[ni][nj] = lim[i][j] + 1;
        q.push({ni, nj});
      }
    }
  }
  /*for ( int i = 1; i <= n; ++i ) {
    for ( int j = 1; j <= n; ++j ) {
      cout << lim[i][j] << " ";
    }
    cout << "\n";
  }*/
  int l = 0, r = lim[xs][ys] - 1;
  while ( r - l > 1 ) {
    int mid = (l + r) / 2;
    if ( check(mid) ) {
      l = mid;
    } else {
      r = mid;
    }
  }
  if ( !check(0) ) {
    cout << "-1\n";
    return 0;
  }
  cout << (check(r) ? r : l) << "\n"; 
  return 0;  
}

• Subtask 1: 95 / 100