| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 895976 |
2023-12-31T09:17:02 Z |
niter |
Maze (JOI23_ho_t3) |
C++14 |
|
1 ms |
348 KB |
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define pb push_back
#define ins insert
#define pii pair<int,int>
#define ff first
#define ss second
#define BAE(x) (x).begin(), (x).end()
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define spac cerr << ' ';
#define entr cerr << endl;
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
using namespace std;
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
ostream& operator<<(ostream& os, pii A){ os << "\n[" << A.ff << ", " << A.ss << "]"; }
inline bool check(int i, int j, int n, int m){
return i >= 0 && j >= 0 && i < n && j < m;
}
const int INF = (int)(1e9);
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
vector<pii> dr;
vector<vector<char>> c;
vector<vector<int>> dis;
vector<vector<bool>> special;
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int n, m, L;
cin >> n >> m >> L;
pii s, t;
cin >> s.ff >> s.ss >> t.ff >> t.ss;
s.ff--; s.ss--; t.ff--; t.ss--;
c = vector<vector<char>>(n, vector<char>(m, ' '));
loop(i,0,n){
loop(j,0,m){
cin >> c[i][j];
}
}
for(int i = -1; i <= 1; i += 2){
for(int j = -1; j <= 1; j += 2){
dr.pb({L * i, L * j});
for(int k = 0; k < L; k ++){
dr.pb({k * i, (L + 1) * j});
dr.pb({(L + 1) * j, k * i});
}
}
}
sort(BAE(dr));
dr.resize(unique(BAE(dr)) - dr.begin());
// STL(dr);
special = vector<vector<bool>>(n, vector<bool>(m, false));
for(auto &i:dr){
int nx = s.ff + i.ff;
int ny = s.ss + i.ss;
if(check(nx, ny, n, m)){
special[nx][ny] = true;
}
}
dis = vector<vector<int>>(n, vector<int>(m, INF));
dis[s.ff][s.ss] = 0;
queue<pii> Q;
Q.push(s);
while(!Q.empty()){
int nowx = Q.front().ff;
int nowy = Q.front().ss;
Q.pop();
if(special[nowx][nowy]) continue;
loop(d,0,4){
int nx = nowx + dx[d];
int ny = nowy + dy[d];
if(!check(nx, ny, n, m)) continue;
if(dis[nx][ny] == INF){
dis[nx][ny] = 1;
Q.push({nx, ny});
}
}
}
// for(auto &i:dis){
// STL(i) entr
// }
priority_queue<pair<int,pii>, vector<pair<int,pii>>, greater<pair<int,pii>>> pq;
loop(i,0,n){
loop(j,0,m){
if(dis[i][j] != INF) pq.push({dis[i][j], {i, j}});
}
}
// pq.push({0, s});
while(!pq.empty()){
int nowx = pq.top().ss.ff;
int nowy = pq.top().ss.ss;
int nowd = pq.top().ff;
pq.pop();
if(nowd != dis[nowx][nowy]) continue;
loop(d,0,4){
int nx = nowx + dx[d];
int ny = nowy + dy[d];
if(!check(nx, ny, n, m)) continue;
if(c[nx][ny] == '#') continue;
if(dis[nx][ny] > nowd){
dis[nx][ny] = nowd;
pq.push({dis[nx][ny], {nx, ny}});
}
}
for(auto &d:dr){
int nx = nowx + d.ff;
int ny = nowy + d.ss;
if(!check(nx, ny, n, m)) continue;
if(dis[nx][ny] > nowd + 1){
dis[nx][ny] = nowd + 1;
pq.push({dis[nx][ny], {nx, ny}});
}
}
}
assert(dis[t.ff][t.ss] != INF);
cout << dis[t.ff][t.ss] << '\n';
}
/*
5 5 2
1 1
4 4
.####
#####
#####
###.#
#####
*/
Compilation message
Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::pair<int, int>)':
Main.cpp:17:86: warning: no return statement in function returning non-void [-Wreturn-type]
17 | ostream& operator<<(ostream& os, pii A){ os << "\n[" << A.ff << ", " << A.ss << "]"; }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
