# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1083698 | hohemhein | Mecho (IOI09_mecho) | C++17 | 128 ms | 7840 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define f first
#define s second
#define pb push_back
#define pu push
#define ll long long
#define int long long
#define endl "\n"
#define all(x) (x).begin() , (x).end()
using namespace std;
const int nmax = 8e2+4;
const int oo = 1e12+3;
const ll mod = 1e9+7;
char m[nmax][nmax];
int bee[nmax][nmax];
bool bear[nmax][nmax];
int mov[] = { 1,-1 };
void llenar(){
for( int i = 0; i < nmax; i++ ){
fill( bee[i], bee[i]+nmax, oo);
}
}
void bfsBee( vector<ii>&aux, int n ){
queue<ii>c;
for( auto [i,j] : aux ){
c.pu({i,j});
bee[i][j] = 0;
}
while( !c.empty() ){
auto [x,y] = c.front();
c.pop();
for( int i = 0; i < 2; i++ )
if( x+mov[i] > 0 && x+mov[i] <= n && m[ x+mov[i] ][y] == 'G' && bee[ x+mov[i] ][y] == oo ){
c.pu( {x+mov[i],y} );
bee[ x+mov[i] ][y] = bee[x][y]+1;
}
for( int i = 0; i < 2; i++ )
if( y+mov[i] > 0 && y+mov[i] <= n && m[x][y+mov[i]] == 'G' && bee[x][y+mov[i]] == oo ){
c.pu( {x,y+mov[i]} );
bee[x][y+mov[i]] = bee[x][y]+1;
}
}
}
void bfsBear( ii X, int n, int k, int op ){
for( int i = 0; i <= n+1; i++ ){
fill( bear[i], bear[i]+n+2, false );
}
queue<iiii>c;
bear[X.f][X.s] = true;
c.pu({ X, {op,1} });
while( !c.empty() ){
auto [x,y] = c.front().f;
auto add = c.front().s.s;
auto pe = c.front().s.f + ( ( (add%k) == 0)?1:0 );
c.pop();
for( int i = 0; i < 2; i++ ){
if( x+mov[i] > 0 && x+mov[i] <= n && m[ x+mov[i] ][y] != 'T' && !bear[ x+mov[i] ][y] && bee[ x+mov[i] ][y] > pe ){
c.pu( { {x+mov[i],y} , {pe,add+1} } );
bear[ x+mov[i] ][y] = true;
}
}
for( int i = 0; i < 2; i++ ){
if( y+mov[i] > 0 && y+mov[i] <= n && m[x][y+mov[i]] != 'T'&& !bear[x][y+mov[i]] && bee[x][y+mov[i]] > pe ){
c.pu( { {x,y+mov[i]}, {pe,add+1} } );
bear[x][y+mov[i]] = true;
}
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie();
//cout << fixed << setprecision(4);
/*ifstream cin ("atlarge.in");
ofstream cout ("atlarge.out");*/
llenar();
int n, k; cin >> n >> k;
ii init, meta;
vector<ii>aux;
for( int i = 1; i <= n; i++ )
for( int j = 1; j <= n; j++ ){
cin >> m[i][j];
if( m[i][j] == 'H' )aux.pb({i,j});
else if( m[i][j] == 'M' )init = {i,j};
else if( m[i][j] == 'D' )meta = {i,j};
}
m[init.f][init.s] = 'G';
bfsBee( aux, n );
int l = 0,r = bee[init.f][init.s];
while( r-l > 1 ){
int m = (r+l)>>1;
bfsBear( init, n, k,m);
if( bear[meta.f][meta.s] )l = m;
else r = m;
/* cout << m <<"\n";
for( int i = 1; i <= n; i++ ){
for( int j = 1; j <= n; j++ )
cout << bear[i][j] <<" ";
cout <<"\n";
}
cout << "\n\n";*/
}
bfsBear( init, n, k, l);
cout << ( ( bear[meta.f][meta.s] )? l : -1 ) <<"\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |