이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)size(x)
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
typedef pair<int, int> pp;
void dbg(){
cerr << endl;
}
template<typename H, typename... T> void dbg(H h, T... t){
cerr << h << ", ";
dbg(t...);
}
void IOS(){
cin.tie(0) -> sync_with_stdio(0);
#ifndef ONLINE_JUDGE
// freopen("inp.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">: ", dbg(__VA_ARGS__)
#else
#define er(...) 0
#endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 1e5 + 5, maxk = 31, lg = 18, inf = ll(1e18) + 5;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dy2[8] = {0, 1, 1, 1, 0, -1, -1, -1}, dx2[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int r, c;
int main(){ IOS();
int n; cin >> r >> c >> n;
pp st, en; cin >> st.ff >> st.ss >> en.ff >> en.ss;
st = {st.ff-1, st.ss-1}, en = {en.ff-1, en.ss-1};
vector<vector<bool>> is(r, vector<bool>(c));
vector<vector<int>> dist(r, vector<int>(c, -1));
vector<vector<int>> dist2(r, vector<int>(c, -1));
rep(i,0,r){
rep(j,0,c){
char x; cin >> x;
is[i][j] = x == '.';
}
}
vector<pp> cand{st};
dist[st.ff][st.ss] = 0;
while(sz(cand)){
int D = dist[cand.back().ff][cand.back().ss];
deque<pp> q;
while(sz(cand)){
q.pb(cand.back());
auto[a, b] = cand.back(); cand.pop_back();
dist2[a][b] = 0;
rep(d,0,4){
int x = a + dx[d], y = b + dy[d];
if(x < 0 || x >= r || y < 0 || y >= c || !is[x][y] || dist[x][y] + 1) continue;
dist[x][y] = D;
cand.pb({x, y});
}
}
int l = 0;
while(l < sz(q)){
auto[a, b] = q.front(); q.pop_front();
if(dist[a][b] == -1){
cand.pb({a, b});
dist[a][b] = D + 1;
}
if(dist2[a][b] < n - 1){
rep(d,0,8){
int x = a + dx2[d], y = b + dy2[d];
if(x < 0 || x >= r || y < 0 || y >= c || dist[x][y] + 1 || dist2[x][y] + 1) continue;
dist2[x][y] = dist2[a][b] + 1;
q.pb({x, y});
}
} else if(dist2[a][b] == n-1){
rep(d,0,4){
int x = a + dx[d], y = b + dy[d];
if(x < 0 || x >= r || y < 0 || y >= c || dist[x][y] + 1 || dist2[x][y] + 1) continue;
dist2[x][y] = dist2[a][b] + 1;
q.pb({x, y});
}
}
}
}
cout << dist[en.ff][en.ss] << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |