#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'
int n,s;
queue<pair<int,int>> ss;
int dist[801][801];
int it[801][801];
vector<int> x={1,-1,0,0};
vector<int> y={0,0,1,-1};
int dd[801][801];
pair<int,int> aa;
pair<int,int> bb;
bool check(int mid){
queue<pair<int,int>> tt;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
dd[i][j]=-1;
}
}
dd[aa.a][aa.b]=0;
tt.push({aa.a,aa.b});
while(tt.size()){
pair<int,int> no=tt.front();
tt.pop();
//if(dd[no.a][no.b])
for(int i=0;i<4;i++){
int xx=no.a+x[i];
int yy=no.b+y[i];
if(xx<0 or xx>=n or yy<0 or yy>=n){
continue;
}
if(it[xx][yy]==0){
continue;
}
if(dd[xx][yy]==-1){
if(dist[xx][yy]!=-1){
if(dist[xx][yy]<=mid-1+(dd[no.a][no.b]+1+s-1)/s){
continue;
}
}
dd[xx][yy]=dd[no.a][no.b]+1;
//cout<<xx<<":"<<yy<<":"<<dd[xx][yy]<<endl;
tt.push({xx,yy});
}
}
}
/*for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<dd[i][j]<<",";
}
cout<<endl;
}
cout<<mid<<":"<<dd[bb.a][bb.b]<<endl;*/
return dd[bb.a][bb.b]!=-1;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>s;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
dist[i][j]=-1;
char s;
cin>>s;
it[i][j]=1;
if(s=='T'){
it[i][j]=0;
}
else if(s=='G'){
}
else if(s=='M'){
aa={i,j};
}
else if(s=='D'){
it[i][j]=0;
bb={i,j};
}
else if(s=='H'){
ss.push({i,j});
dist[i][j]=0;
}
}
}
while(ss.size()){
pair<int,int> no=ss.front();
ss.pop();
for(int i=0;i<4;i++){
int xx=no.a+x[i];
int yy=no.b+y[i];
if(xx<0 or xx>=n or yy<0 or yy>=n){
continue;
}
if(it[xx][yy]==0){
continue;
}
if(dist[xx][yy]==-1){
dist[xx][yy]=dist[no.a][no.b]+1;
ss.push({xx,yy});
}
}
}
int low=0;
int high=dist[aa.a][aa.b]-1;
it[bb.a][bb.b]=1;
if(check(low)==false){
cout<<-1<<endl;
}
else{
while(low<high-1){
int mid=(low+high)/2;
if(check(mid)){
low=mid;
}
else{
high=mid;
}
}
int ans=low;
if(check(high)){
ans=max(ans,high);
}
cout<<ans<<endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
2 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
3 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
4 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
128 ms |
8568 KB |
Output is correct |
8 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
1 ms |
896 KB |
Output is correct |
13 |
Correct |
1 ms |
768 KB |
Output is correct |
14 |
Correct |
1 ms |
916 KB |
Output is correct |
15 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
16 |
Correct |
1 ms |
512 KB |
Output is correct |
17 |
Incorrect |
1 ms |
640 KB |
Output isn't correct |
18 |
Correct |
1 ms |
640 KB |
Output is correct |
19 |
Incorrect |
1 ms |
640 KB |
Output isn't correct |
20 |
Correct |
1 ms |
640 KB |
Output is correct |
21 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
22 |
Correct |
1 ms |
768 KB |
Output is correct |
23 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
24 |
Correct |
1 ms |
768 KB |
Output is correct |
25 |
Incorrect |
1 ms |
948 KB |
Output isn't correct |
26 |
Correct |
1 ms |
896 KB |
Output is correct |
27 |
Incorrect |
1 ms |
1024 KB |
Output isn't correct |
28 |
Correct |
1 ms |
1024 KB |
Output is correct |
29 |
Incorrect |
1 ms |
1024 KB |
Output isn't correct |
30 |
Correct |
1 ms |
1024 KB |
Output is correct |
31 |
Incorrect |
1 ms |
1024 KB |
Output isn't correct |
32 |
Correct |
1 ms |
1024 KB |
Output is correct |
33 |
Incorrect |
9 ms |
3712 KB |
Output isn't correct |
34 |
Correct |
11 ms |
3712 KB |
Output is correct |
35 |
Correct |
34 ms |
3712 KB |
Output is correct |
36 |
Incorrect |
12 ms |
4224 KB |
Output isn't correct |
37 |
Correct |
15 ms |
4224 KB |
Output is correct |
38 |
Correct |
47 ms |
4324 KB |
Output is correct |
39 |
Incorrect |
14 ms |
4736 KB |
Output isn't correct |
40 |
Correct |
17 ms |
4736 KB |
Output is correct |
41 |
Correct |
60 ms |
4736 KB |
Output is correct |
42 |
Incorrect |
20 ms |
5248 KB |
Output isn't correct |
43 |
Correct |
21 ms |
5248 KB |
Output is correct |
44 |
Correct |
71 ms |
5248 KB |
Output is correct |
45 |
Incorrect |
21 ms |
5888 KB |
Output isn't correct |
46 |
Correct |
24 ms |
5880 KB |
Output is correct |
47 |
Correct |
88 ms |
5888 KB |
Output is correct |
48 |
Incorrect |
25 ms |
6400 KB |
Output isn't correct |
49 |
Correct |
29 ms |
6400 KB |
Output is correct |
50 |
Correct |
107 ms |
6392 KB |
Output is correct |
51 |
Incorrect |
27 ms |
6892 KB |
Output isn't correct |
52 |
Correct |
34 ms |
6912 KB |
Output is correct |
53 |
Correct |
132 ms |
6912 KB |
Output is correct |
54 |
Incorrect |
33 ms |
7416 KB |
Output isn't correct |
55 |
Correct |
38 ms |
7416 KB |
Output is correct |
56 |
Correct |
155 ms |
7544 KB |
Output is correct |
57 |
Incorrect |
37 ms |
7936 KB |
Output isn't correct |
58 |
Correct |
46 ms |
7936 KB |
Output is correct |
59 |
Correct |
178 ms |
8056 KB |
Output is correct |
60 |
Incorrect |
41 ms |
8440 KB |
Output isn't correct |
61 |
Correct |
49 ms |
8448 KB |
Output is correct |
62 |
Correct |
206 ms |
8448 KB |
Output is correct |
63 |
Correct |
153 ms |
8444 KB |
Output is correct |
64 |
Correct |
275 ms |
8440 KB |
Output is correct |
65 |
Correct |
268 ms |
8568 KB |
Output is correct |
66 |
Incorrect |
198 ms |
8440 KB |
Output isn't correct |
67 |
Correct |
59 ms |
8440 KB |
Output is correct |
68 |
Correct |
88 ms |
8568 KB |
Output is correct |
69 |
Correct |
66 ms |
8568 KB |
Output is correct |
70 |
Correct |
67 ms |
8568 KB |
Output is correct |
71 |
Correct |
65 ms |
8568 KB |
Output is correct |
72 |
Correct |
63 ms |
8568 KB |
Output is correct |
73 |
Correct |
61 ms |
8824 KB |
Output is correct |
74 |
Correct |
127 ms |
8840 KB |
Output is correct |
75 |
Correct |
119 ms |
8764 KB |
Output is correct |
76 |
Correct |
116 ms |
8840 KB |
Output is correct |
77 |
Correct |
112 ms |
8824 KB |
Output is correct |
78 |
Correct |
64 ms |
8696 KB |
Output is correct |
79 |
Correct |
108 ms |
8696 KB |
Output is correct |
80 |
Correct |
105 ms |
8696 KB |
Output is correct |
81 |
Correct |
111 ms |
8696 KB |
Output is correct |
82 |
Correct |
98 ms |
8732 KB |
Output is correct |
83 |
Correct |
117 ms |
8824 KB |
Output is correct |
84 |
Correct |
133 ms |
8824 KB |
Output is correct |
85 |
Correct |
119 ms |
8700 KB |
Output is correct |
86 |
Correct |
125 ms |
8776 KB |
Output is correct |
87 |
Correct |
122 ms |
8696 KB |
Output is correct |
88 |
Correct |
123 ms |
8700 KB |
Output is correct |
89 |
Correct |
149 ms |
8684 KB |
Output is correct |
90 |
Correct |
137 ms |
8728 KB |
Output is correct |
91 |
Correct |
150 ms |
8664 KB |
Output is correct |
92 |
Correct |
135 ms |
8724 KB |
Output is correct |