#include <bits/stdc++.h>
#define int int64_t
using namespace std;
int N, S;
char forest[1000][1000];
int btime[1000][1000];
int mtime[1000][1000];
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};
struct src{
int x, y;
int step;
src(int x, int y, int step) : x(x), y(y), step(step){};
};
int32_t main()
{
cin >> N >> S;
queue<src> bfs;
int si, sj;
int hi, hj;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
cin >> forest[i][j];
btime[i][j]=1e9;
if(forest[i][j]=='H'){
bfs.push(src(i, j, 0));
btime[i][j]=0;
}
if(forest[i][j]=='M'){
si = i;
sj = j;
}
if(forest[i][j]=='D'){
hi=i; hj=j;
}
}
}
while(!bfs.empty()){
int x = bfs.front().x;
int y = bfs.front().y;
int step = bfs.front().step;
bfs.pop();
for(int i = 0; i < 4; i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(nx<1 || nx>N || ny<1 || ny>N) continue;
if(forest[nx][ny]=='T' || forest[nx][ny]=='D') continue;
if(step+1<btime[nx][ny]){
btime[nx][ny]=step+1;
bfs.push(src(nx, ny, step+1));
}
}
}
int lo = 0;
int hig = 1000000;
lo--;
while(lo<hig){
int mid = lo+(hig-lo+1)/2;
queue<src> bfs2;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
mtime[i][j]=1e9;
}
}
bfs2.push({si, sj, mid*S});
mtime[si][sj]=mid*S;
bool possible = false;
while(!bfs2.empty()){
int x = bfs2.front().x;
int y = bfs2.front().y;
int step = bfs2.front().step;
if(x==hi && y==hj){
possible = true;
break;
}
bfs2.pop();
for(int i = 0; i < 4; i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(nx<1 || nx>N || ny<1 || ny>N) continue;
if(forest[nx][ny]=='T' || forest[nx][ny]=='H') continue;
if(step+1>mtime[nx][ny]) continue;
int minute = (int)ceil((step+1)/(double)(S));
if( minute<=btime[nx][ny]){
mtime[nx][ny]=step+1;
bfs2.push(src(nx, ny, step+1));
}
}
}
if(possible){
lo = mid;
}else{
hig = mid-1;
}
}
cout << lo;
return 0;
}
Compilation message
mecho.cpp: In function 'int32_t main()':
mecho.cpp:80:26: warning: 'hj' may be used uninitialized in this function [-Wmaybe-uninitialized]
80 | if(x==hi && y==hj){
| ~^~~~
mecho.cpp:80:17: warning: 'hi' may be used uninitialized in this function [-Wmaybe-uninitialized]
80 | if(x==hi && y==hj){
| ~^~~~
mecho.cpp:74:22: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
74 | mtime[si][sj]=mid*S;
| ~~~~~~~~~~~~~^~~~~~
mecho.cpp:74:22: warning: 'si' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Incorrect |
0 ms |
4444 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
4444 KB |
Output isn't correct |
| 5 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 6 |
Correct |
0 ms |
4444 KB |
Output is correct |
| 7 |
Runtime error |
87 ms |
65536 KB |
Execution killed with signal 9 |
| 8 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 9 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 10 |
Correct |
0 ms |
4440 KB |
Output is correct |
| 11 |
Correct |
0 ms |
4444 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 13 |
Runtime error |
90 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
69 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 16 |
Correct |
0 ms |
4444 KB |
Output is correct |
| 17 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 18 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 19 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 20 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 21 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 22 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 23 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 24 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 25 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 26 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 27 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 28 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 29 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 30 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 31 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 32 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 33 |
Incorrect |
7 ms |
12892 KB |
Output isn't correct |
| 34 |
Correct |
6 ms |
12864 KB |
Output is correct |
| 35 |
Runtime error |
68 ms |
65536 KB |
Execution killed with signal 9 |
| 36 |
Incorrect |
8 ms |
12892 KB |
Output isn't correct |
| 37 |
Correct |
7 ms |
13000 KB |
Output is correct |
| 38 |
Runtime error |
104 ms |
65536 KB |
Execution killed with signal 9 |
| 39 |
Incorrect |
11 ms |
12888 KB |
Output isn't correct |
| 40 |
Correct |
9 ms |
12888 KB |
Output is correct |
| 41 |
Runtime error |
77 ms |
65536 KB |
Execution killed with signal 9 |
| 42 |
Incorrect |
12 ms |
13144 KB |
Output isn't correct |
| 43 |
Correct |
11 ms |
13148 KB |
Output is correct |
| 44 |
Runtime error |
73 ms |
65536 KB |
Execution killed with signal 9 |
| 45 |
Incorrect |
14 ms |
15196 KB |
Output isn't correct |
| 46 |
Correct |
13 ms |
15196 KB |
Output is correct |
| 47 |
Runtime error |
90 ms |
65536 KB |
Execution killed with signal 9 |
| 48 |
Incorrect |
16 ms |
17240 KB |
Output isn't correct |
| 49 |
Correct |
16 ms |
17244 KB |
Output is correct |
| 50 |
Runtime error |
75 ms |
65536 KB |
Execution killed with signal 9 |
| 51 |
Incorrect |
20 ms |
17240 KB |
Output isn't correct |
| 52 |
Correct |
18 ms |
17244 KB |
Output is correct |
| 53 |
Runtime error |
77 ms |
65536 KB |
Execution killed with signal 9 |
| 54 |
Incorrect |
23 ms |
17496 KB |
Output isn't correct |
| 55 |
Correct |
27 ms |
17488 KB |
Output is correct |
| 56 |
Runtime error |
82 ms |
65536 KB |
Execution killed with signal 9 |
| 57 |
Incorrect |
26 ms |
17568 KB |
Output isn't correct |
| 58 |
Correct |
24 ms |
17500 KB |
Output is correct |
| 59 |
Runtime error |
83 ms |
65536 KB |
Execution killed with signal 9 |
| 60 |
Incorrect |
28 ms |
17488 KB |
Output isn't correct |
| 61 |
Correct |
27 ms |
17488 KB |
Output is correct |
| 62 |
Runtime error |
95 ms |
65536 KB |
Execution killed with signal 9 |
| 63 |
Correct |
78 ms |
17488 KB |
Output is correct |
| 64 |
Correct |
125 ms |
17500 KB |
Output is correct |
| 65 |
Correct |
105 ms |
17500 KB |
Output is correct |
| 66 |
Incorrect |
98 ms |
17720 KB |
Output isn't correct |
| 67 |
Correct |
80 ms |
17488 KB |
Output is correct |
| 68 |
Correct |
46 ms |
17492 KB |
Output is correct |
| 69 |
Correct |
45 ms |
17500 KB |
Output is correct |
| 70 |
Correct |
43 ms |
17488 KB |
Output is correct |
| 71 |
Correct |
40 ms |
17488 KB |
Output is correct |
| 72 |
Incorrect |
36 ms |
17488 KB |
Output isn't correct |
| 73 |
Runtime error |
88 ms |
65536 KB |
Execution killed with signal 9 |
| 74 |
Runtime error |
84 ms |
65536 KB |
Execution killed with signal 9 |
| 75 |
Runtime error |
97 ms |
65536 KB |
Execution killed with signal 9 |
| 76 |
Runtime error |
94 ms |
65536 KB |
Execution killed with signal 9 |
| 77 |
Runtime error |
90 ms |
65536 KB |
Execution killed with signal 9 |
| 78 |
Runtime error |
86 ms |
65536 KB |
Execution killed with signal 9 |
| 79 |
Runtime error |
84 ms |
65536 KB |
Execution killed with signal 9 |
| 80 |
Runtime error |
85 ms |
65536 KB |
Execution killed with signal 9 |
| 81 |
Runtime error |
86 ms |
65536 KB |
Execution killed with signal 9 |
| 82 |
Runtime error |
84 ms |
65536 KB |
Execution killed with signal 9 |
| 83 |
Runtime error |
87 ms |
65536 KB |
Execution killed with signal 9 |
| 84 |
Runtime error |
88 ms |
65536 KB |
Execution killed with signal 9 |
| 85 |
Runtime error |
98 ms |
65536 KB |
Execution killed with signal 9 |
| 86 |
Runtime error |
92 ms |
65536 KB |
Execution killed with signal 9 |
| 87 |
Runtime error |
87 ms |
65536 KB |
Execution killed with signal 9 |
| 88 |
Runtime error |
84 ms |
65536 KB |
Execution killed with signal 9 |
| 89 |
Runtime error |
84 ms |
65536 KB |
Execution killed with signal 9 |
| 90 |
Runtime error |
105 ms |
65536 KB |
Execution killed with signal 9 |
| 91 |
Runtime error |
101 ms |
65536 KB |
Execution killed with signal 9 |
| 92 |
Runtime error |
108 ms |
65536 KB |
Execution killed with signal 9 |
