#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define int short
#define ld double
#define pii pair<int,int>
#define rand() abs((rand()<<15)|rand())
#define randll() abs(((long long)rand()<<30)|rand())
const int MOD = 1000000007;
char grid[805][805];
int dist1[805][805];
pair<int,int> dist3[805][805];
int dist2[805][805];
int dist[805][805];
int vis[805][805];
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long seed;
asm("rdtsc" : "=A"(seed));
srand(seed);
int n, s;
cin >> n >> s;
int si, sj;
int fi, fj;
vector<pair<int,int>> p;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cin >> grid[i][j];
if(grid[i][j]=='J') {
si = i;
sj = j;
}
if(grid[i][j]=='H') {
fi = i;
fj = j;
}
if(grid[i][j]=='P') {
p.push_back({i,j});
}
if(grid[i][j]=='B') grid[i][j]=0;
}
}
vector<int> di = {1,0,-1,0};
vector<int> dj = {0,1,0,-1};
queue<pair<int,pair<int,int>>> q;
memset(dist1,-1,sizeof(dist1));
dist1[si][sj]=0;
q.push({0,{si,sj}});
while(!q.empty()) {
int d = q.front().first;
int i = q.front().second.first;
int j = q.front().second.second;
q.pop();
for(int x = 0; x < 4; x++) {
if(grid[i+di[x]][j+dj[x]] == 0) continue;
if(dist1[i+di[x]][j+dj[x]] != -1) continue;
dist1[i+di[x]][j+dj[x]] = d+1;
q.push({d+1,{i+di[x],j+dj[x]}});
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dist1[i][j]>0) {
dist3[i][j] = {(dist1[i][j]+s-1)/s,(dist1[i][j]+s-1)%s};
}
memset(dist2,-1,sizeof(dist2));
for(auto pp: p) {
int pi = pp.first;
int pj = pp.second;
dist2[pi][pj]=0;
q.push({0,{pi,pj}});
}
while(!q.empty()) {
int d = q.front().first;
int i = q.front().second.first;
int j = q.front().second.second;
q.pop();
for(int x = 0; x < 4; x++) {
if(grid[i+di[x]][j+dj[x]] == 0) continue;
if(dist2[i+di[x]][j+dj[x]] != -1) continue;
if(grid[i+di[x]][j+dj[x]] == 'H') continue;
dist2[i+di[x]][j+dj[x]] = d+1;
q.push({d+1,{i+di[x],j+dj[x]}});
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dist1[i][j]>=0) {
dist[i][j] = dist2[i][j]-dist3[i][j].first-(dist3[i][j].second==s-1);
}
// for(int i = 1; i <= n; i++) {
// for(int j = 1; j <= n; j++) {
// cerr << dist3[i][j].first << ":" << dist3[i][j].second << " ";
// }
// cerr << endl;
// }
// cerr << endl;
// for(int i = 1; i <= n; i++) {
// for(int j = 1; j <= n; j++) {
// cerr << dist2[i][j] << " ";
// }
// cerr << endl;
// }
// cerr << endl;
// for(int i = 1; i <= n; i++) {
// for(int j = 1; j <= n; j++) {
// cerr << dist[i][j] << " ";
// }
// cerr << endl;
// }
// cerr << endl;
priority_queue<pair<int,pair<int,int>>> pq;
pq.push({dist[si][sj], {si, sj}});
int ans = dist[si][sj];
bool toBreak = 0;
while(!pq.empty()) {
int d = pq.top().first;
int i = pq.top().second.first;
int j = pq.top().second.second;
pq.pop();
ans = min(ans, d);
if(i==fi && j == fj) break;
for(int x = 0; x < 4; x++) {
if(grid[i+di[x]][j+dj[x]] == 'H') {toBreak = 1; break;}
if(grid[i+di[x]][j+dj[x]] == 0) continue;
if(dist1[i+di[x]][j+dj[x]] <= 0) continue;
if(vis[i+di[x]][j+dj[x]]) continue;
vis[i+di[x]][j+dj[x]] = 1;
pq.push({dist[i+di[x]][j+dj[x]],{i+di[x],j+dj[x]}});
}
if(toBreak)break;
}
cout << ans << endl;
}
Compilation message
mecho.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("unroll-loops")
mecho.cpp:14:17: warning: overflow in implicit constant conversion [-Woverflow]
const int MOD = 1000000007;
^~~~~~~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:141:17: warning: 'fj' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(i==fi && j == fj) break;
~~^~~~~
mecho.cpp:141:7: warning: 'fi' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(i==fi && j == fj) break;
~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
2 |
Incorrect |
3 ms |
2944 KB |
Output isn't correct |
3 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
4 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
5 |
Correct |
5 ms |
2944 KB |
Output is correct |
6 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
7 |
Incorrect |
12 ms |
3456 KB |
Output isn't correct |
8 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
9 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
10 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
11 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
12 |
Incorrect |
5 ms |
2944 KB |
Output isn't correct |
13 |
Correct |
4 ms |
2944 KB |
Output is correct |
14 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
15 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
16 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
17 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
18 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
19 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
20 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
21 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
22 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
23 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
24 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
25 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
26 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
27 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
28 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
29 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
30 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
31 |
Incorrect |
5 ms |
2944 KB |
Output isn't correct |
32 |
Incorrect |
4 ms |
2944 KB |
Output isn't correct |
33 |
Incorrect |
6 ms |
3200 KB |
Output isn't correct |
34 |
Incorrect |
6 ms |
3200 KB |
Output isn't correct |
35 |
Incorrect |
6 ms |
3200 KB |
Output isn't correct |
36 |
Incorrect |
7 ms |
3200 KB |
Output isn't correct |
37 |
Incorrect |
6 ms |
3200 KB |
Output isn't correct |
38 |
Incorrect |
6 ms |
3200 KB |
Output isn't correct |
39 |
Incorrect |
7 ms |
3200 KB |
Output isn't correct |
40 |
Incorrect |
7 ms |
3200 KB |
Output isn't correct |
41 |
Incorrect |
7 ms |
3200 KB |
Output isn't correct |
42 |
Incorrect |
9 ms |
3328 KB |
Output isn't correct |
43 |
Incorrect |
7 ms |
3328 KB |
Output isn't correct |
44 |
Incorrect |
10 ms |
3328 KB |
Output isn't correct |
45 |
Incorrect |
8 ms |
3328 KB |
Output isn't correct |
46 |
Incorrect |
8 ms |
3328 KB |
Output isn't correct |
47 |
Incorrect |
8 ms |
3328 KB |
Output isn't correct |
48 |
Incorrect |
9 ms |
3328 KB |
Output isn't correct |
49 |
Incorrect |
10 ms |
3456 KB |
Output isn't correct |
50 |
Incorrect |
9 ms |
3328 KB |
Output isn't correct |
51 |
Incorrect |
10 ms |
3456 KB |
Output isn't correct |
52 |
Incorrect |
9 ms |
3456 KB |
Output isn't correct |
53 |
Incorrect |
9 ms |
3456 KB |
Output isn't correct |
54 |
Incorrect |
10 ms |
3456 KB |
Output isn't correct |
55 |
Incorrect |
10 ms |
3456 KB |
Output isn't correct |
56 |
Incorrect |
10 ms |
3456 KB |
Output isn't correct |
57 |
Incorrect |
11 ms |
3456 KB |
Output isn't correct |
58 |
Incorrect |
11 ms |
3456 KB |
Output isn't correct |
59 |
Incorrect |
12 ms |
3456 KB |
Output isn't correct |
60 |
Incorrect |
13 ms |
3584 KB |
Output isn't correct |
61 |
Incorrect |
13 ms |
3556 KB |
Output isn't correct |
62 |
Incorrect |
13 ms |
3584 KB |
Output isn't correct |
63 |
Correct |
12 ms |
3456 KB |
Output is correct |
64 |
Incorrect |
12 ms |
3584 KB |
Output isn't correct |
65 |
Incorrect |
12 ms |
3584 KB |
Output isn't correct |
66 |
Incorrect |
13 ms |
3584 KB |
Output isn't correct |
67 |
Incorrect |
12 ms |
3456 KB |
Output isn't correct |
68 |
Correct |
13 ms |
3576 KB |
Output is correct |
69 |
Incorrect |
12 ms |
3584 KB |
Output isn't correct |
70 |
Incorrect |
13 ms |
3584 KB |
Output isn't correct |
71 |
Incorrect |
12 ms |
3584 KB |
Output isn't correct |
72 |
Incorrect |
12 ms |
3584 KB |
Output isn't correct |
73 |
Incorrect |
12 ms |
3456 KB |
Output isn't correct |
74 |
Incorrect |
12 ms |
3456 KB |
Output isn't correct |
75 |
Incorrect |
12 ms |
3456 KB |
Output isn't correct |
76 |
Incorrect |
13 ms |
3456 KB |
Output isn't correct |
77 |
Incorrect |
12 ms |
3584 KB |
Output isn't correct |
78 |
Incorrect |
12 ms |
3456 KB |
Output isn't correct |
79 |
Incorrect |
12 ms |
3456 KB |
Output isn't correct |
80 |
Incorrect |
13 ms |
3456 KB |
Output isn't correct |
81 |
Incorrect |
12 ms |
3584 KB |
Output isn't correct |
82 |
Incorrect |
12 ms |
3456 KB |
Output isn't correct |
83 |
Correct |
12 ms |
3584 KB |
Output is correct |
84 |
Incorrect |
12 ms |
3456 KB |
Output isn't correct |
85 |
Incorrect |
12 ms |
3584 KB |
Output isn't correct |
86 |
Incorrect |
13 ms |
3584 KB |
Output isn't correct |
87 |
Incorrect |
12 ms |
3584 KB |
Output isn't correct |
88 |
Correct |
13 ms |
3584 KB |
Output is correct |
89 |
Incorrect |
13 ms |
3584 KB |
Output isn't correct |
90 |
Incorrect |
13 ms |
3584 KB |
Output isn't correct |
91 |
Incorrect |
13 ms |
3584 KB |
Output isn't correct |
92 |
Incorrect |
14 ms |
3584 KB |
Output isn't correct |