// #include "maze.h"
#include<bits/stdc++.h>
using namespace std;
#define V vector
#define rep(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define Int long long
#define all(x) (x).begin(), (x).end()
#define pii pair<int,int>
#define ff first
#define ss second
#if VANWIJ
#define DBG 0
#else
#define DBG 0
#endif
#define cerr if(DBG) cout
#define dbg(x) cerr << "?" << #x << " : " << x << endl;
#define _ << " " <<
const int INF = 1e9;
int r, c, n;
// start and goal
int sx, sy, gx, gy;
V<V<char>> a;
V<V<int>> nxth, nxtv;
int findH(int i,int j){
if(nxth[i][j]==j) return j;
return nxth[i][j] = findH(i, nxth[i][j]);
}
int findV(int i,int j){
if(nxtv[i][j]==i) return i;
return nxtv[i][j] = findV(nxtv[i][j], j);
}
V<V<int>> dist;
V<V<bool>> vis;
int minimum_stamps(int _r,int _c,int _n,int _sx,int _sy,int _gx,int _gy,V<V<char>>_a){
r = _r; c = _c; n = _n;
sx = _sx; sy = _sy; gx = _gx; gy = _gy;
a.swap(_a);
nxth = V<V<int>>(r+2, V<int>(c+2));
nxtv = V<V<int>>(r+2, V<int>(c+2));
rep(i,0,r+2) rep(j,0,c+2){
nxth[i][j] = j;
nxtv[i][j] = i;
}
dist = V<V<int>>(r, V<int>(c,INF));
vis = V<V<bool>>(r, V<bool>(c));
int ans = INF;
V<pii> que[2];
que[0].push_back({sx, sy});
for(int d=0; ; d++){
if(ans<=d) break;
dbg(d);
while(!que[d&1].empty()){
auto[x,y] = que[d&1].back(); que[d&1].pop_back();
if(vis[x][y]) continue;
vis[x][y] = 1;
cerr << x _ y << endl;
if(x==gx && y==gy){
ans = min(ans, d); break;
}
// go to empty neighbour
for(int dir : {1,3,5,7}){
int i = x+dir%3-1, j = y+dir/3-1;
if(0<=i && i<r && 0<=j && j<c && a[i][j]=='.' && d<dist[i][j]){
que[d&1].push_back({i, j});
}
}
// goal is in stamp proximity
bool nearGoal = 0;
nearGoal |= abs(gx-x)<=n && abs(gy-y)<n;
nearGoal |= abs(gx-x)<n && abs(gy-y)<=n;
if(nearGoal){
dbg(x); dbg(y);
ans = min(ans, d+1);
}
// go to stamp perimeter
// for(int i=x-n; i<=x+n; i++) if(0<=i && i<r)
// for(int j=y-n; j<=y+n; j++) if(0<=j && j<c)
// if(!(abs(i-x)==n && abs(j-y)==n))
// {
// que[~d&1].push({i,j});
// }
// (x+n, ..)
{
int i=min(x+n,r-1), j=max(y-(n-1),0);
j = findH(i,j);
while(j <= min(y+(n-1),c-1)){
if(d+1 < dist[i][j]){
que[~d&1].push_back({i, j}); dist[i][j] = d+1;
}
nxth[i][j] = j+1;
j = findH(i,j);
}
}
// (x-n, ..)
{
int i=max(x-n,0), j=max(y-(n-1),0);
j = findH(i,j);
while(j <= min(y+(n-1),c-1)){
if(d+1 < dist[i][j]){
que[~d&1].push_back({i, j}); dist[i][j] = d+1;
}
nxth[i][j] = j+1;
j = findH(i,j);
}
}
// (.., y+n)
{
int i=max(x-(n-1),0), j=min(y+n,c-1);
i = findV(i,j);
while(i <= min(x+(n-1),r-1)){
if(d+1 < dist[i][j]){
que[~d&1].push_back({i, j}); dist[i][j] = d+1;
}
nxtv[i][j] = i+1;
i = findV(i,j);
}
}
// (.., y-n)
{
int i=max(x-(n-1),0), j=max(y-n,0);
i = findV(i,j);
while(i <= min(x+(n-1),r-1)){
if(d+1 < dist[i][j]){
que[~d&1].push_back({i, j}); dist[i][j] = d+1;
}
nxtv[i][j] = i+1;
i = findV(i,j);
}
}
}
}
return ans;
}
int main() {
int R, C, N, Sr, Sc, Gr, Gc;
assert(3 == scanf("%d %d %d", &R, &C, &N));
assert(2 == scanf("%d %d", &Sr, &Sc));
assert(2 == scanf("%d %d", &Gr, &Gc));
std::vector<std::vector<char>> A(R, std::vector<char>(C));
for (int i = 0; i < R; ++i) {
getchar(); // Read endline
for (int j = 0; j < C; ++j) {
scanf("%c", &A[i][j]);
}
}
printf("%d\n", minimum_stamps(R, C, N, Sr, Sc, Gr, Gc, A));
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:180:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
180 | scanf("%c", &A[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
