#include <bits/stdc++.h> using namespace std ; typedef long long ll ; typedef long double ld ; typedef pair<int, int> pii ; typedef pair<int, long long> pil ; typedef pair<long long, int> pli ; typedef pair<long long, long long> pll ; #define bitc(n) (__builtin_popcountll(n)) #define clz(n) (__builtin_clzll(n)) #define ctz(n) (__builtin_ctzll(n)) #define lgi(n) (31 - __builtin_clz(n)) #define lgl(n) (63 - __builtin_clzll(n)) #define MASK(k) (1ll << (k)) #define getbit(n, k) ((n) >> (k) & 1) #define flipbit(n, k) ((n) ^ (1ll << (k))) #define ton(n, k) ((n) | (1ll << (k))) #define toff(n, k) ((n) & ~(1ll << (k))) #define fi first #define se second #define mp make_pair #define eb emplace_back #define lwb lower_bound #define upb upper_bound #define sz(x) (int)(x.size()) #define all(x) x.begin(),x.end() #define taskname "maze" template<class X, class Y> bool maximize(X &x, const Y &y) { if(x < y) { return x = y, true ; } return false ; } template<class X, class Y> bool minimize(X &x, const Y &y) { if(x > y) { return x = y, true ; } return false ; } template<class X> void removeDup(vector<X> &ve) { sort(ve.begin(), ve.end()) ; ve.resize(unique(ve.begin(), ve.end()) - ve.begin()) ; } const ll INF = 1e18 ; const int inf = 1e9 ; const int mod = 1e9 + 7 ; const int N = 3e3 + 5, M = 6e6 + 5, LG = 17 ; const int X[] = {-1, 1, 0, 0} ; const int Y[] = {0, 0, 1, -1} ; /* Some Peach Tea Is Great ;-; */ /* Author : Tuandq */ vector<bool> a[N] ; int r, c, n ; pii st, en ; bool inside(const int &i, const int &j) { return 0 < i && i <= r && 0 < j && j <= c ; } int dis[M] ; bitset<M> vis ; int encode(const int &i, const int &j) { return (i - 1) * c + j - 1 ; } pii decode(const int &x) { return mp(x / c + 1, x % c + 1) ; } namespace sub1 { bool checkSub() { return n == 1 ; } void solve() { memset(dis, 0x0f, sizeof dis) ; deque<int> q ; dis[encode(st.fi, st.se)] = 0 ; q.emplace_back(encode(st.fi, st.se)) ; while(!q.empty()) { int u = q.front() ; q.pop_front() ; if(vis[u]) continue ; vis.set(u) ; pii cur = decode(u) ; for(int d = 0; d < 4; d ++) { int x = cur.fi + X[d] ; int y = cur.se + Y[d] ; if(!inside(x, y)) continue ; int w = !a[x][y] ; int nxt = encode(x, y) ; if(minimize(dis[nxt], dis[u] + w)) { if(!w) q.emplace_front(nxt) ; else q.emplace_back(nxt) ; } } } cout << dis[encode(en.fi, en.se)] ; } } namespace sub2 { bool checkSub() { return r * c <= 1e3 ; } void solve() { memset(dis, 0x0f, sizeof dis) ; deque<int> q ; dis[encode(st.fi, st.se)] = 0 ; q.emplace_back(encode(st.fi, st.se)) ; while(!q.empty()) { int u = q.front() ; q.pop_front() ; if(vis[u]) continue ; vis.set(u) ; pii cur = decode(u) ; for(int d = 0; d < 4; d ++) { int x = cur.fi + X[d] ; int y = cur.se + Y[d], nxt = encode(x, y) ; if(inside(x, y) && a[x][y] && minimize(dis[nxt], dis[u])) { q.emplace_front(nxt) ; } } for(int x = cur.fi - n; x <= cur.fi + n; x ++) { for(int y = cur.se - n; y <= cur.se + n; y ++) { if(inside(x, y) && mp(x, y) != cur) { if(abs(cur.fi - x) + abs(cur.se - y) == (n << 1)) continue ; int nxt = encode(x, y) ; if(minimize(dis[nxt], dis[u] + 1)) { q.emplace_back(nxt) ; } } } } } cout << dis[encode(en.fi, en.se)] ; } } namespace sub3 { int mask = 0 ; void update(const pii &cur) { if(cur.fi >= en.fi && cur.se >= en.se) mask |= 1 ; if(cur.fi >= en.fi && cur.se <= en.se) mask |= 2 ; if(cur.fi <= en.fi && cur.se >= en.se) mask |= 4 ; if(cur.fi <= en.fi && cur.se <= en.se) mask |= 8 ; } void solve() { queue<int> q ; vis.set(encode(st.fi, st.se)) ; q.emplace(encode(st.fi, st.se)) ; for(int res = 0; res < 11;) { queue<int> nxt ; while(!q.empty()) { int u = q.front() ; q.pop() ; pii cur = decode(u) ; update(cur) ; if(cur == en || mask == 15) return cout << res, void() ; int cnt = 0 ; for(int d = 0; d < 4; d ++) { int x = cur.fi + X[d] ; int y = cur.se + Y[d], nxt = encode(x, y) ; if(inside(x, y) && a[x][y] && !vis[nxt]) { vis.set(nxt) ; q.emplace(nxt) ; ++ cnt ; } } /*if(!cnt) */nxt.emplace(u) ; } swap(q, nxt) ; ++ res ; // cerr << "PHASE " << res << endl ; // for(int i = 1; i <= r; i ++) { // for(int j = 1; j <= c; j ++) cerr << vis[encode(i, j)] << ' ' ; // cerr << endl ; // } // cerr << endl ; while(!q.empty()) { int u = q.front() ; q.pop() ; pii cur = decode(u) ; update(cur) ; if(cur == en || mask == 15) return cout << res, void() ; for(int p = -n + 1; p < n; p ++) { for(int d = 0; d < 4; d ++) { int x = cur.fi + X[d] * n ; int y = cur.se + Y[d] * n ; if(!X[d]) x += p ; else y += p ; x = (x < 1 ? 1 : (x > r ? r : x)) ; y = (y < 1 ? 1 : (y > c ? c : y)) ; int g = encode(x, y) ; if(inside(x, y) && !vis[g]) { vis.set(g) ; nxt.emplace(g) ; } } } } swap(nxt, q) ; } assert(false) ; } } void kittncool() { cin >> r >> c >> n >> st.fi >> st.se >> en.fi >> en.se ; for(int i = 1; i <= r; i ++) { a[i].assign(c + 2, false) ; for(int j = 1; j <= c; j ++) { char t ; cin >> t ; if(t == '.') a[i][j] = true ; } } // if(sub1::checkSub()) return sub1::solve() ; // if(sub2::checkSub()) return sub2::solve() ; return sub3::solve() ; } signed main() { ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ; if(fopen(taskname".inp", "r")) { freopen(taskname".inp", "r", stdin) ; // freopen(taskname".out", "w", stdout) ; } int t = 1 ; //cin >> t ; while(t --) { kittncool() ; } }

Main.cpp: In function 'int main()':
Main.cpp:251:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  251 |         freopen(taskname".inp", "r", stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~