# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
# define pb push_back
# define pf push_front
# define For(i, a, b) for( int i = a; i < b; i++ )
# define in insert
# define all(a) a.begin(),a.end()
# define pi pair < int, int >
# define DEBUG
# define readfile(file) freopen ( (file + ".in").c_str(), "r", stdin)
# define writefile(file) freopen ( (file + ".out").c_str(), "w", stdout)
# define speed ios_base::sync_with_stdio(false);cin.tie(NULL)
# define LARGE (1e7)
# define SET(file) readfile(file);writefile(file);
using namespace std;
int n, s, cnt, ans = -1;
int visited[805][805], step[805][805], check[805];
vector < string > forest, forest1, forest2;
string m;
pi pos = {-1, -1};
pi add[] = { {1, 0}, {-1, 0}, {0, -1}, {0, 1} };
int valid ( pi pos ){
int i = pos.fi, j = pos.se;
if ( i >= 0 && i < n && j >= 0 && j < n && forest[i][j] != 'T' )
return 1;
return 0;
}
void spread(){
vector < pi > pos;
For ( i, 0, n )
For ( j, 0, n )
if ( forest[i][j] == 'H' )
pos.pb( {i, j} );
For ( i, 0, pos.size() )
For ( j, 0, 4 ){
pi to = { pos[i].fi + add[j].fi, pos[i].se + add[j].se };
if ( valid(to) && forest[to.fi][to.se] != 'D' ){
forest[to.fi][to.se] = 'H';
cnt++;
}
}
}
int main(){
/// Author: _Dilshod_
speed;
cin >> n >> s;
For ( i, 0, n ){
cin >> m;
forest.pb(m);
forest1.pb(m);
if ( pos.fi == -1 )
For ( j, 0, m.size() )
if ( m[j] == 'M' )
pos = {i, j};
}
for ( int x = 0; x > -1; x++ ){
For ( i, 0, 805 )
For ( j, 0, 805 ){
visited[i][j] = 0;
step[i][j] = 0;
check[j] = 0;
}
queue < pi > BFS;
BFS.push(pos);
visited[pos.fi][pos.se] = 1;
forest = forest1;
cnt = 0;
int ans1 = -1;
For ( i, 0, x ){
spread();
if ( !cnt )
break;
cnt = 0;
}
while( !BFS.empty() ){
pi loc = BFS.front();
BFS.pop();
visited[loc.fi][loc.se] = 1;
int st = step[loc.fi][loc.se];
if ( forest[loc.fi][loc.se] == 'D' ){
ans1 = x;
break;
}
if ( forest[loc.fi][loc.se] == 'H' )
continue;
if ( !(st % s) && st != 0 && !check[st] ){
forest2 = forest;
spread();
if ( forest[loc.fi][loc.se] == 'H' ){
forest = forest2;
continue;
}
check[st] = 1;
}
For ( i, 0, 4 ){
pi to = { loc.fi + add[i].fi, loc.se + add[i].se };
if ( valid( to ) && !visited[to.fi][to.se] ){
visited[to.fi][to.se] = 1;
step[to.fi][to.se] = st + 1;
BFS.push(to);
}
}
}
if ( ans1 == -1 )
break;
ans = max( ans, ans1 );
}
cout << ans;
}
Compilation message
mecho.cpp: In function 'void spread()':
mecho.cpp:7:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
# define For(i, a, b) for( int i = a; i < b; i++ )
mecho.cpp:45:11:
For ( i, 0, pos.size() )
~~~~~~~~~~~~~~~~
mecho.cpp:45:5: note: in expansion of macro 'For'
For ( i, 0, pos.size() )
^~~
mecho.cpp: In function 'int main()':
mecho.cpp:7:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
# define For(i, a, b) for( int i = a; i < b; i++ )
mecho.cpp:67:19:
For ( j, 0, m.size() )
~~~~~~~~~~~~~~
mecho.cpp:67:13: note: in expansion of macro 'For'
For ( j, 0, m.size() )
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5368 KB |
Output is correct |
| 2 |
Correct |
10 ms |
5368 KB |
Output is correct |
| 3 |
Correct |
11 ms |
5460 KB |
Output is correct |
| 4 |
Correct |
11 ms |
5368 KB |
Output is correct |
| 5 |
Correct |
8 ms |
5368 KB |
Output is correct |
| 6 |
Correct |
9 ms |
5368 KB |
Output is correct |
| 7 |
Execution timed out |
1072 ms |
11948 KB |
Time limit exceeded |
| 8 |
Correct |
7 ms |
5496 KB |
Output is correct |
| 9 |
Correct |
19 ms |
5496 KB |
Output is correct |
| 10 |
Correct |
14 ms |
5368 KB |
Output is correct |
| 11 |
Correct |
16 ms |
5368 KB |
Output is correct |
| 12 |
Execution timed out |
1080 ms |
5496 KB |
Time limit exceeded |
| 13 |
Correct |
10 ms |
5496 KB |
Output is correct |
| 14 |
Correct |
9 ms |
5496 KB |
Output is correct |
| 15 |
Correct |
270 ms |
5624 KB |
Output is correct |
| 16 |
Correct |
117 ms |
5624 KB |
Output is correct |
| 17 |
Correct |
578 ms |
5624 KB |
Output is correct |
| 18 |
Correct |
205 ms |
5464 KB |
Output is correct |
| 19 |
Execution timed out |
1047 ms |
5596 KB |
Time limit exceeded |
| 20 |
Correct |
337 ms |
5496 KB |
Output is correct |
| 21 |
Execution timed out |
1080 ms |
5496 KB |
Time limit exceeded |
| 22 |
Execution timed out |
1077 ms |
5496 KB |
Time limit exceeded |
| 23 |
Execution timed out |
1078 ms |
5516 KB |
Time limit exceeded |
| 24 |
Execution timed out |
1079 ms |
5496 KB |
Time limit exceeded |
| 25 |
Execution timed out |
1081 ms |
5368 KB |
Time limit exceeded |
| 26 |
Execution timed out |
1086 ms |
5496 KB |
Time limit exceeded |
| 27 |
Execution timed out |
1080 ms |
5500 KB |
Time limit exceeded |
| 28 |
Execution timed out |
1072 ms |
5496 KB |
Time limit exceeded |
| 29 |
Execution timed out |
1084 ms |
5596 KB |
Time limit exceeded |
| 30 |
Execution timed out |
1069 ms |
5596 KB |
Time limit exceeded |
| 31 |
Execution timed out |
1068 ms |
5504 KB |
Time limit exceeded |
| 32 |
Execution timed out |
1080 ms |
5624 KB |
Time limit exceeded |
| 33 |
Execution timed out |
1063 ms |
5880 KB |
Time limit exceeded |
| 34 |
Execution timed out |
1072 ms |
6108 KB |
Time limit exceeded |
| 35 |
Correct |
31 ms |
5880 KB |
Output is correct |
| 36 |
Execution timed out |
1086 ms |
6236 KB |
Time limit exceeded |
| 37 |
Execution timed out |
1089 ms |
6136 KB |
Time limit exceeded |
| 38 |
Correct |
38 ms |
6136 KB |
Output is correct |
| 39 |
Execution timed out |
1091 ms |
6268 KB |
Time limit exceeded |
| 40 |
Execution timed out |
1078 ms |
6264 KB |
Time limit exceeded |
| 41 |
Correct |
47 ms |
6264 KB |
Output is correct |
| 42 |
Execution timed out |
1076 ms |
6520 KB |
Time limit exceeded |
| 43 |
Execution timed out |
1080 ms |
6500 KB |
Time limit exceeded |
| 44 |
Correct |
51 ms |
6392 KB |
Output is correct |
| 45 |
Execution timed out |
1081 ms |
6648 KB |
Time limit exceeded |
| 46 |
Execution timed out |
1068 ms |
6776 KB |
Time limit exceeded |
| 47 |
Correct |
62 ms |
6648 KB |
Output is correct |
| 48 |
Execution timed out |
1049 ms |
6904 KB |
Time limit exceeded |
| 49 |
Execution timed out |
1062 ms |
6984 KB |
Time limit exceeded |
| 50 |
Correct |
74 ms |
7032 KB |
Output is correct |
| 51 |
Execution timed out |
1079 ms |
7160 KB |
Time limit exceeded |
| 52 |
Execution timed out |
1086 ms |
7160 KB |
Time limit exceeded |
| 53 |
Correct |
85 ms |
7288 KB |
Output is correct |
| 54 |
Execution timed out |
1063 ms |
7416 KB |
Time limit exceeded |
| 55 |
Execution timed out |
1085 ms |
7388 KB |
Time limit exceeded |
| 56 |
Correct |
94 ms |
7416 KB |
Output is correct |
| 57 |
Execution timed out |
1072 ms |
7800 KB |
Time limit exceeded |
| 58 |
Execution timed out |
1082 ms |
7672 KB |
Time limit exceeded |
| 59 |
Correct |
108 ms |
7824 KB |
Output is correct |
| 60 |
Execution timed out |
1074 ms |
8056 KB |
Time limit exceeded |
| 61 |
Execution timed out |
1082 ms |
8056 KB |
Time limit exceeded |
| 62 |
Correct |
142 ms |
8056 KB |
Output is correct |
| 63 |
Execution timed out |
1075 ms |
8992 KB |
Time limit exceeded |
| 64 |
Execution timed out |
1074 ms |
8184 KB |
Time limit exceeded |
| 65 |
Execution timed out |
1061 ms |
8800 KB |
Time limit exceeded |
| 66 |
Execution timed out |
1064 ms |
9204 KB |
Time limit exceeded |
| 67 |
Execution timed out |
1067 ms |
9220 KB |
Time limit exceeded |
| 68 |
Execution timed out |
1059 ms |
11756 KB |
Time limit exceeded |
| 69 |
Execution timed out |
1055 ms |
9712 KB |
Time limit exceeded |
| 70 |
Execution timed out |
1062 ms |
14268 KB |
Time limit exceeded |
| 71 |
Execution timed out |
1031 ms |
12184 KB |
Time limit exceeded |
| 72 |
Execution timed out |
1034 ms |
9780 KB |
Time limit exceeded |
| 73 |
Execution timed out |
1051 ms |
14964 KB |
Time limit exceeded |
| 74 |
Execution timed out |
1024 ms |
14568 KB |
Time limit exceeded |
| 75 |
Execution timed out |
1082 ms |
15000 KB |
Time limit exceeded |
| 76 |
Execution timed out |
1069 ms |
15052 KB |
Time limit exceeded |
| 77 |
Execution timed out |
1079 ms |
15104 KB |
Time limit exceeded |
| 78 |
Execution timed out |
1076 ms |
15004 KB |
Time limit exceeded |
| 79 |
Execution timed out |
1071 ms |
14540 KB |
Time limit exceeded |
| 80 |
Execution timed out |
1045 ms |
14920 KB |
Time limit exceeded |
| 81 |
Execution timed out |
1068 ms |
15016 KB |
Time limit exceeded |
| 82 |
Execution timed out |
1065 ms |
14868 KB |
Time limit exceeded |
| 83 |
Execution timed out |
1062 ms |
15016 KB |
Time limit exceeded |
| 84 |
Execution timed out |
1079 ms |
12208 KB |
Time limit exceeded |
| 85 |
Execution timed out |
1082 ms |
15016 KB |
Time limit exceeded |
| 86 |
Execution timed out |
1073 ms |
15096 KB |
Time limit exceeded |
| 87 |
Execution timed out |
1078 ms |
14864 KB |
Time limit exceeded |
| 88 |
Execution timed out |
1066 ms |
15108 KB |
Time limit exceeded |
| 89 |
Execution timed out |
1049 ms |
11920 KB |
Time limit exceeded |
| 90 |
Execution timed out |
1081 ms |
14904 KB |
Time limit exceeded |
| 91 |
Execution timed out |
1062 ms |
12328 KB |
Time limit exceeded |
| 92 |
Execution timed out |
1073 ms |
14944 KB |
Time limit exceeded |
