# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
541302 | SquareSpoon | Mecho (IOI09_mecho) | C++14 | 137 ms | 5936 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <algorithm>
#define MAX 801
using namespace std;
typedef pair<int, int> pii;
int n, m, d[MAX][MAX];
char map[MAX][MAX];
bool v[MAX][MAX];
int x[5] = {1, 0, -1, 0};
int y[5] = {0, 1, 0, -1};
//calcular o tempo em passos
void bees(vector<pii> c){
queue<pii> q;
for(int i = 0; i < c.size(); i++){
q.push(c[i]);
d[c[i].first][c[i].second] = m;
}
while(!q.empty()){
pii node = q.front();
q.pop();
if(v[node.first][node.second]) continue;
v[node.first][node.second] = true;
for(int i = 0; i < 4; i++){
int x1 = x[i] + node.first;
int y1 = y[i] + node.second;
if(x1 > n || x1 < 1 || y1 > n || y1 < 1) continue;
if(v[x1][y1]) continue;
if(d[x1][y1] > d[node.first][node.second] + 1 || d[x1][y1] == 0) d[x1][y1] = d[node.first][node.second] + m;
q.push(make_pair(x1, y1));
}
}
}
int bfs(int c1, int c2, int steps, int time){
queue<pair<int, pii > > q;
bool v2[MAX][MAX];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) v2[i][j] = false;
q.push(make_pair(time, make_pair(c1, c2)));
while(!q.empty()){
pii node = q.front().second;
int stps = q.front().first;
q.pop();
if(v2[node.first][node.second]) continue;
v2[node.first][node.second] = true;
for(int i = 0; i < 4; i++){
int x1 = x[i] + node.first;
int y1 = y[i] + node.second;
if(x1 < 1 || x1 > n || y1 < 1 || y1 > n) continue;
//cout << x1 << " " << y1 << " " << d[x1][y1] << " " << map[x1][y1] << " " << v2[x1][y1] << '\n';
if(v2[x1][y1] || map[x1][y1] == 'T' || d[x1][y1] <= stps || map[x1][y1] == 'H' || map[x1][y1] == 'M') continue;
//cout << stps << '\n';
//cout << x1 << " " << y1 << " " << d[x1][y1] << '\n';
if(map[x1][y1] == 'D'){
//cout << "found" << '\n';
int res = stps/m;
return res;
}
q.push(make_pair(stps+1, make_pair(x1, y1)));
}
}
return -1;
}
int main(){
cin >> n >> m;
vector<pii> cords;
int xs, ys, xs1, ys1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin >> map[i][j];
if(map[i][j] == 'H'){
cords.push_back(make_pair(i, j));
} else if(map[i][j] == 'D'){
xs = i, ys = j;
} else if(map[i][j] == 'M'){
xs1 = i, ys1 = j;
}
}
}
bees(cords);
int limit = 0;
for(int i = 0; i < 4; i++){
int x1 = xs + x[i];
int y1 = ys + y[i];
if(x1 > n || x1 < 1 || y1 < 1 || y1 > n) continue;
limit = max(limit, d[x1][y1]);
}
int l = 1, r = (limit - m)/m;
int mid = (l+r)/2;
int res = -1;
int path;
d[xs][ys] = MAX*m;
while(l <= r){
path = bfs(xs1, ys1, m, mid*m);
//cout << path << '\n';
if(path == -1){
r = mid - 1;
} else{
l = mid + 1;
res = max(res, mid);
}
//cout << mid << " ";
mid = (l+r)/2;
path = 0;
}
cout << res-1 << '\n';
//cout << path << " " << time << '\n';
/*for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cout << d[i][j] << " ";
}
cout << '\n';
}*/
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |