This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ldb,ldb> pdd;
#define ff(i,a,b) for(int i = a; i <= b; i++)
#define fb(i,b,a) for(int i = b; i >= a; i--)
#define trav(a,x) for(auto& a : x)
#define sz(a) (int)(a).size()
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k) print the k-th smallest number in os(0-based)
const int mod = 1000000007;
const int inf = 1e9 + 5;
const int mxN = 200005;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int n, m, k;
int Sx, Sy;
int Gx, Gy;
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> k >> Sx >> Sy >> Gx >> Gy;
vector<string> s(n + 1);
ff(i,1,n)cin >> s[i], s[i] = ' ' + s[i];
vector<vector<vector<int>>> d(n + 1, vector<vector<int>>(m + 1, vector<int>(2)));
ff(i,1,n)ff(j,1,m)ff(l,0,1)d[i][j][l] = inf;
deque<array<int,3>> que; que.push_front({Sx, Sy, 0});
d[Sx][Sy][0] = 0;
while(sz(que)){
auto [x, y, z] = que.front(); que.pop_front();
if(z == 0){
ff(i,0,3){
int nwx = x + dx[i];
int nwy = y + dy[i];
if(nwx >= 1 && nwx <= n && nwy >= 1 && nwy <= m){
if(s[nwx][nwy] == '.'){
if(d[nwx][nwy][0] > d[x][y][0]){
d[nwx][nwy][0] = d[x][y][0];
que.push_front({nwx, nwy, 0});
}
}
else{
if(d[nwx][nwy][1] > d[x][y][0]){
d[nwx][nwy][1] = d[x][y][0];
que.push_front({nwx, nwy, 1});
}
}
}
}
}
else{
ff(nwx,max(1,x - k + 1),min(n,x + k - 1)){
ff(nwy,max(1,y - k + 1),min(m,y + k - 1)){
if(d[nwx][nwy][0] > d[x][y][1] + 1){
d[nwx][nwy][0] = d[x][y][1] + 1;
que.push_back({nwx, nwy, 0});
}
}
}
}
}
cout << d[Gx][Gy][0] << '\n';
return 0;
}
/*
2 4 2
1 1
2 4
.###
###.
6 6 1
1 6
6 1
..#.#.
##.###
####.#
...###
##.##.
.#.###
6 7 6
6 4
3 1
..#.#.#
##.##..
.######
#..#.#.
.######
..#.##.
1 15 1
1 15
1 1
...............
// probati bojenje sahovski
*/
# | 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... |