| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 806816 |
2023-08-04T10:03:43 Z |
someone |
Maze (JOI23_ho_t3) |
C++14 |
|
1 ms |
340 KB |
#include <bits/stdc++.h>
//#define int long long
#define x first
#define y second
using namespace std;
const int N = 6e6 + 42, INF = 1e9 + 42;
int dl[] = {0, 0, 1, -1},
dc[] = {1, -1, 0, 0},
trans[] = {0, 0, 0, 0};
bool etat[N], vu[N];
int row, col, n, ldeb, cdeb, lfin, cfin, ans = INF, dist[N], lhor[N], rhor[N], lver[N], rver[N];
inline bool valid(int l, int c) {
return -1 < l && l < row && -1 < c && c < col;
}
void BFS() {
deque<pair<int, int>> dq;
dist[ldeb * col + cdeb] = 0;
dq.push_front({ldeb, cdeb});
while(!dq.empty()) {
auto act = dq[0];
dq.pop_front();
int id = act.x * col + act.y;
if(!vu[id]) {
vu[id] = true;
int dx = abs(lfin - act.x), dy = abs(cfin - act.y);
if(dx <= n && dy <= n && dx + dy != 2*n)
ans = min(ans, dist[id]+1);
for(int i = 0; i < 4; i++) {
int x = act.x + dl[i], y = act.y + dc[i], j = id + trans[i];
if(valid(x, y) && etat[j] && !vu[j]) {
dq.push_front({x, y});
dist[j] = dist[id];
}
}
//(act.x - n, act.y - n + 1) - (act.x - n, act.y + n - 1)
//(act.x + n, act.y - n + 1) - (act.x + n, act.y + n - 1)
for(int j = act.y - n + 1; j <= act.y + n - 1; j++) {
if(valid(act.x - n, j)) {
dq.push_back({act.x - n, j});
dist[(act.x - n) * col + j] = min(dist[(act.x - n) * col + j], dist[id]+1);
}
if(valid(act.x + n, j)) {
dq.push_back({act.x + n, j});
dist[(act.x + n) * col + j] = min(dist[(act.x + n) * col + j], dist[id]+1);
}
}
//(act.x - n + 1, act.y - n) - (act.x + n - 1, act.y - n)
//(act.x - n + 1, act.y + n) - (act.x + n - 1, act.y + n)
for(int i = act.x - n + 1; i <= act.x + n - 1; i++) {
if(valid(i, act.y - n)) {
dq.push_back({i, act.y - n});
dist[i * col + act.y - n] = min(dist[i * col + act.y - n], dist[id]+1);
}
if(valid(i, act.y + n)) {
dq.push_back({i, act.y + n});
dist[i * col + act.y + n] = min(dist[i * col + act.y + n], dist[id]+1);
}
}
//(act.x - n, act.y - n + 1) - (act.x - n, act.y + n - 1)
/*int l = (act.y + n) / (2 * n - 1) - 1;
if(act.x >= n) {
int i = (act.x - n) * col + l;
if(l != -1) {
int pos = (act.x - n) * col + rhor[i],
sup = max(lhor[i], act.y - n + 1);
while(rhor[i] >= sup) {
dist[pos] = min(dist[pos], dist[id]+1);
dq.push_back({act.x - n, rhor[i]});
pos--;
rhor[i]--;
}
}
i++;
if((2 * n - 1) * (l+1) < col) {
int pos = (act.x - n) * col + lhor[i],
inf = min(rhor[i], act.y + n - 1);
while(lhor[i] <= inf) {
dist[pos] = min(dist[pos], dist[id]+1);
dq.push_back({act.x - n, lhor[i]});
pos++;
lhor[i]++;
}
}
}
//(act.x + n, act.y - n + 1) - (act.x + n, act.y + n - 1)
if(act.x + n < row) {
int i = (act.x + n) * col + l;
if(l != -1) {
int pos = (act.x + n) * col + rhor[i],
sup = max(lhor[i], act.y - n + 1);
while(rhor[i] >= sup) {
dist[pos] = min(dist[pos], dist[id]+1);
dq.push_back({act.x + n, rhor[i]});
pos--;
rhor[i]--;
}
}
i++;
if((2 * n - 1) * (l+1) < col) {
int pos = (act.x + n) * col + lhor[i],
inf = min(rhor[i], act.y + n - 1);
while(lhor[i] <= inf) {
dist[pos] = min(dist[pos], dist[id]+1);
dq.push_back({act.x + n, lhor[i]});
pos++;
lhor[i]++;
}
}
}
//(act.x - n + 1, act.y - n) - (act.x + n - 1, act.y - n)
int h = (act.x + n) / (2 * n - 1) - 1;
if(act.y >= n) {
int i = h * col + (act.y - n);
if(h != -1) {
int pos = rver[i] * col + act.y - n,
sup = max(lver[i], act.x - n + 1);
while(rver[i] >= sup) {
dist[pos] = min(dist[pos], dist[id]+1);
dq.push_back({rver[i], act.y - n});
pos -= col;
rver[i]--;
}
}
i += col;
if((2 * n - 1) * (h+1) < row) {
int pos = lver[i] * col + act.y - n,
inf = min(rver[i], act.x + n - 1);
while(lver[i] <= inf) {
dist[pos] = min(dist[pos], dist[id]+1);
dq.push_back({lver[i], act.y - n});
pos += col;
lver[i]++;
}
}
}
//(act.x - n + 1, act.y + n) - (act.x + n - 1, act.y + n)
if(act.y + n < col) {
int i = h * col + (act.y + n);
if(h != -1) {
int pos = rver[i] * col + act.y + n,
sup = max(lver[i], act.x - n + 1);
while(rver[i] >= sup) {
dist[pos] = min(dist[pos], dist[id]+1);
dq.push_back({rver[i], act.y + n});
pos -= col;
rver[i]--;
}
}
i += col;
if((2 * n - 1) * (h+1) < row) {
int pos = lver[i] * col + act.y + n,
inf = min(rver[i], act.x + n - 1);
while(lver[i] <= inf) {
dist[pos] = min(dist[pos], dist[id]+1);
dq.push_back({lver[i], act.y + n});
pos += col;
lver[i]++;
}
}
}*/
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> row >> col >> n >> ldeb >> cdeb >> lfin >> cfin;
ldeb--, cdeb--, lfin--, cfin--;
for(int i = 0; i < 4; i++)
trans[i] = dl[i] * row + dc[i];
for(int i = 0; i < row*col; i++)
dist[i] = INF;
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++) {
char c; cin >> c;
etat[i * col + j] = (c == '.');
}
for(int i = 0; i < row; i++)
for(int j = 0; (2*n-1)*j < col; j++) {
lhor[i * col + j] = (2*n-1)*j;
rhor[i * col + j] = min((2*n-1)*(j+1), col)-1;
}
for(int i = 0; (2*n-1)*i < row; i++)
for(int j = 0; j < col; j++) {
lver[i * col + j] = (2*n-1)*i;
rver[i * col + j] = min((2*n-1)*(i+1), row)-1;
}
BFS();
ans = min(ans, dist[lfin * col + cfin]);
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
328 KB |
Output is correct |
| 3 |
Correct |
1 ms |
328 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
328 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
328 KB |
Output is correct |
| 3 |
Correct |
1 ms |
328 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
328 KB |
Output is correct |
| 3 |
Correct |
1 ms |
328 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
