/*Code by TMQ*/ #include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define ld long double #define ii pair<int, int> #define fi first #define se second #define pb push_back #define em emplace #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++) #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++) #define FIV(i, a, b) for (int i = (a), _b = (b); i >= _b; i--) #define all(x) (x).begin(), (x).end() #define reset(a, x) (memset(a, x, sizeof(a))); #define Unique(v) v.erase(unique(all(v)), v.end()); #define testcase \ int tc; \ cin >> tc; \ while (tc--) \ solve(); #define howlong cerr << "Time elapsed: " << fixed << setprecision(9) << (double)clock() / CLOCKS_PER_SEC << "s"; #define what_is(x) cerr << #x << " is " << x << '\n'; ll inline GCD(ll a, ll b) { return !b ? abs(a) : GCD(b, a % b); } ll inline LCM(ll a, ll b) { return (a / GCD(a, b) * b); } template <class X, class Y> bool maximize(X &x, Y y) { if (x < y) { x = y; return true; } return false; }; template <class X, class Y> bool minimize(X &x, Y y) { if (x > y) { x = y; return true; } return false; }; ///=====================================s======================================== #define BIT(i, mask) ((mask >> (i)) & 1) #define DAOBIT(i, mask) ((mask ^ (1 << i))) #define OFFBIT(i, mask) ((mask & ~(1 << (i)))) #define ONBIT(i, mask) ((mask(1 << (i)))) ///============================================================================ void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifndef ONLINE_JUDGE #define debug(x...) \ { \ cerr << "[" << #x << "] = ["; \ _print(x); \ } #else #define debug(x...) #endif ///============================================================================ void TASK(string task) { if (fopen((task + ".inp").c_str(), "r")) { freopen((task + ".inp").c_str(), "r", stdin); freopen((task + ".out").c_str(), "w", stdout); } } ///============================================================================ const int mod = 1e9 + 7; const int inf = 1e9 + 10; const int nmax = 3e6 + 5; ///============================================================================ int R, C, N; int sx, sy, ex, ey; vector<vector<char>> a; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; bool is_valid(int x, int y) { return 1 <= x && x <= R && 1 <= y && y <= C; } bool check0() { queue<ii> q; q.push({sx, sy}); vector<vector<int>> dist(R + 1, vector<int>(C + 1, -1)); dist[sx][sy] = 0; while (!q.empty()) { ii x = q.front(); q.pop(); int u = x.fi, v = x.se; for (int k = 0; k < 4; k++) { int nu = u + dx[k]; int nv = v + dy[k]; if (is_valid(nu, nv) && a[nu][nv] == '.') { int d = dist[u][v] + 1; if (dist[nu][nv] == -1) { dist[nu][nv] = d; q.push({nu, nv}); } } } } return dist[ex][ey] != -1; } namespace sub1 { void solve() { vector<vector<int>> dist(R + 1, vector<int>(C + 1, inf)); deque<ii> dq; dist[sx][sy] = 0; dq.push_front({sx, sy}); while (!dq.empty()) { ii t = dq.front(); int x = t.fi, y = t.se; dq.pop_front(); for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (is_valid(nx, ny)) { int w = (a[nx][ny] == '#'); int nd = dist[x][y] + w; if (dist[nx][ny] > nd) { dist[nx][ny] = nd; if (w == 0) dq.push_front({nx, ny}); else dq.push_back({nx, ny}); } } } } cout << dist[ex][ey] << '\n'; } } namespace sub2 { bool inside(int x, int y) { return 1 <= x && x <= R && 1 <= y && y <= C; } void solve() { vector<vector<int>> dist(R + 1, vector<int>(C + 1, inf)); deque<ii> dq; dist[sx][sy] = 0; dq.push_front({sx, sy}); while (!dq.empty()) { ii x = dq.front(); dq.pop_front(); int u = x.fi, v = x.se; for (int k = 0; k < 4; k++) { int nu = u + dx[k]; int nv = v + dy[k]; if (inside(nu, nv) && a[nu][nv] == '.') { if (minimize(dist[nu][nv], dist[u][v])) dq.push_front({nu, nv}); } } // for(int i = u - N; i <= u + N; i++) // for(int j = v - N; j <= v + N; j++) // { // if(i == u && j == v) // continue; // if(!inside(i, j)) // continue; // if(abs(i - u) + abs(j - v) <= N << 1) // { // if(minimize(dist[i][j], dist[u][v] + 1)) // { // dq.push_back({i, j}); // } // } for (int i = u - N; i <= u + N; i++) { for (int dj : {-1, 1}) { int j = v + dj * N; if (i == u && j == v) continue; int x = i, y = j; maximize(x, 1); maximize(y, 1); minimize(x, R); minimize(y, C); if (x == u && y == v) continue; if (!inside(x, y)) continue; if (abs(x - u) + abs(y - v) <= N << 1) { if (minimize(dist[x][y], dist[u][v] + 1)) { dq.push_back({x, y}); } } } } for (int j = v - N; j <= v + N; j++) { for (int di : {-1, 1}) { int i = u + di * N; if (i == u && j == v) continue; int x = i, y = j; maximize(x, 1); maximize(y, 1); minimize(x, R); minimize(y, C); if (x == u && y == v) continue; if (!inside(x, y)) continue; if (abs(x - u) + abs(y - v) <= N << 1) { if (minimize(dist[x][y], dist[u][v] + 1)) { dq.push_back({x, y}); } } } } } cout << dist[ex][ey] << '\n'; } } ///============================================================================ int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); TASK("MINESHAFT"); cin >> R >> C >> N; cin >> sx >> sy >> ex >> ey; a.assign(R + 1, vector<char>(C + 1)); for (int i = 1; i <= R; i++) { for (int j = 1; j <= C; j++) { cin >> a[i][j]; } } if (check0()) { cout << 0; return 0; } if (N == 1) { sub1::solve(); return 0; } sub2::solve(); }

Main.cpp: In function 'void TASK(std::string)':
Main.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen((task + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen((task + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~