#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 long long
#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
salesman.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("unroll-loops")
salesman.cpp: In function 'int main()':
salesman.cpp:141:17: warning: 'fj' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(i==fi && j == fj) break;
~~^~~~~
salesman.cpp:141:7: warning: 'fi' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(i==fi && j == fj) break;
~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
13 ms |
10752 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
13 ms |
10752 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
14 ms |
10624 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
13 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
29 ms |
608 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
100 ms |
1116 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
234 ms |
1528 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
431 ms |
2552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
584 ms |
3416 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
838 ms |
5880 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
849 ms |
6656 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
809 ms |
7508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
833 ms |
7956 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
720 ms |
10524 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
673 ms |
9848 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
787 ms |
9692 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
13 ms |
10724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
13 ms |
10752 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
8 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
15 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 21 |
Runtime error |
16 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 22 |
Runtime error |
28 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 23 |
Runtime error |
28 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 24 |
Runtime error |
28 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 25 |
Runtime error |
426 ms |
2140 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 26 |
Runtime error |
713 ms |
3704 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 27 |
Runtime error |
852 ms |
5756 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 28 |
Runtime error |
862 ms |
6620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 29 |
Runtime error |
661 ms |
8184 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 30 |
Runtime error |
672 ms |
8952 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
