#include<bits/stdc++.h> using namespace std; //===================================================================================================================================== #define ll long long #define ld long double #define fi first #define se second #define pb push_back #define pll pair<ll, ll> #define pli pair<ll, int> #define pil pair<int, ll> #define pii pair<int, int> #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)))) #define nmax 1000007 //===================================================================================================================================== const int N = 1e6 + 7; const ll mod = 1e9 + 6; const ll MOD = 1e9 + 7; const ll inf = 1e9; int r, c, n; int sx, sy, ex, ey; vector<vector<char>> a; vector<vector<int>> dp; //===================================================================================================================================== void fre(){ freopen("MINESHAFT.INP", "r", stdin); freopen("MINESHAFT.out", "w", stdout); } ll gcd(ll a, ll b){ return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b){ return (a / gcd(a, b)) * b; } int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; void sub1(){ deque<pii> dq; dp.assign(r + 10, vector<int>(c + 10, inf)); dp[sx][sy] = 0; dq.push_front({sx, sy}); while(!dq.empty()){ pii e = dq.front(); int x = e.fi; int y = e.se; dq.pop_front(); for(int p = 0; p < 4; p++){ int nx = x + dx[p]; int ny = y + dy[p]; if(nx < 1 || nx > r || ny < 1 || ny > c) continue; if(dp[x][y] + (a[nx][ny] == '#') < dp[nx][ny]){ dp[nx][ny] = dp[x][y] + (a[nx][ny] == '#'); if((a[nx][ny] != '#')) dq.push_front({nx, ny}); else dq.push_back({nx, ny}); } } } cout << dp[ex][ey] << '\n'; } namespace sub2{ int ans = inf; int d[1007][1007]; int cal(ll N, ll sx, ll sy, ll ex, ll ey){ ll lx1 = sx - (N - 1), rx1 = sx; ll ly1 = sy - (N - 1), ry1 = sy; ll lx2 = ex - (N - 1), rx2 = ex; ll ly2 = ey - (N - 1), ry2 = ey; auto gap = [](ll l1, ll r1, ll l2, ll r2) -> ll { if (r1 < l2) return l2 - r1; if (r2 < l1) return l1 - r2; return 0; }; ll dx = gap(lx1, rx1, lx2, rx2); ll dy = gap(ly1, ry1, ly2, ry2); ll D = max(dx, dy); if (D == 0) return 1; ll steps = (D + N - 1) / N; return steps + 1; } void solve(){ vector<pii> d1, d2; queue<pii> q; q.push({sx, sy}); d[sx][sy] = 1; while(!q.empty()){ pii e = q.front(); int x = e.fi; int y = e.se; d1.pb({x, y}); if(x == ex && y == ey){ cout << 0 << '\n'; return; } q.pop(); for(int p = 0; p < 4; p++){ int nx = x + dx[p]; int ny = y + dy[p]; if(nx < 1 || nx > r || ny < 1 || ny > c) continue; if(d[nx][ny]){ continue; } if(a[nx][ny] == '#') continue; d[nx][ny] = 1; q.push({nx, ny}); } } q.push({ex, ey}); d[ex][ey] = 1; while(!q.empty()){ pii e = q.front(); int x = e.fi; int y = e.se; d2.pb({x, y}); q.pop(); for(int p = 0; p < 4; p++){ int nx = x + dx[p]; int ny = y + dy[p]; if(nx < 1 || nx > r || ny < 1 || ny > c) continue; if(d[nx][ny]){ continue; } if(a[nx][ny] == '#') continue; d[nx][ny] = 1; q.push({nx, ny}); } } for(auto x : d1){ for(auto y : d2){ ans = min(ans, cal(n, x.fi, x.se, y.fi, y.se)); // cout << x.fi << ' ' << x.se << ' '; // cout << y.fi << ' ' << y.se << ' '; // cout << cal(n, x.fi, x.se, y.fi, y.se) << '\n'; } } cout << ans << '\n'; } } //===================================================================================================================================== int main(){ cin.tie(0)->sync_with_stdio(0); // fre(); cin >> r >> c >> n; cin >> sx >> sy >> ex >> ey; a.resize(r + 10, vector<char>(c + 10)); for(int i = 1; i <= r; i++){ for(int j = 1; j <= c; j++){ cin >> a[i][j]; } } if(n == 1){ sub1(); return 0; } if(r * c <= 1e3){ sub2 :: solve(); return 0; } return 0; }

Main.cpp: In function 'void fre()':
Main.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen("MINESHAFT.INP", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("MINESHAFT.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~