#pragma target("arch=icelake-server")
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <bitset>
using namespace std;
typedef long long ll;
typedef long double ld;
int log_ = 21;
int inf = 1000000007;
long long mod = 998244353;
int p = 499;
int NADIYA = 39;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
int i_st, j_st;
cin >> i_st >> j_st;
i_st--;
j_st--;
int i_f, j_f;
cin >> i_f >> j_f;
i_f--;
j_f--;
vector <int> deep;
vector <string> vs(n);
for (int i = 0; i < n; i++)
cin >> vs[i];
int X = 2;
int c = 1;
int sz = 0;
int K = 2 * k - 1;
while (c * X <= K)
{
c *= X;
sz++;
}
sz++;
vector <vector <vector<int>>> bin(n);
vector <vector <int>> g(n*m*(2*sz));
for (int i = 0; i < n; i++)
{
bin[i].resize(m);
for (int j = 0; j < m; j++)
{
bin[i][j].resize(sz);
}
}
int f = 0;
vector <pair <int, int>> vp(n * m);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
bin[i][j][0] = f;
vp[f] = { i , j };
f++;
}
}
int f2 = f;
int y = 1;
for (int k_ = 1; k_ < sz; k_ ++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
bin[i][j][k_] = f;
g[f].resize(X);
for (int x = 0; x < X; x++)
{
g[f][x] = bin[i][min(j + y * x, m - 1)][k_ - 1];
}
f++;
}
}
y *= X;
}
y /= X;
vector <vector <vector<int>>> bin2(n);
for (int i = 0; i < n; i++)
{
bin2[i].resize(m);
for (int j = 0; j < m; j++)
{
bin2[i][j].resize(sz);
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
bin2[i][j][0] = bin[i][j][0];
}
}
y = 1;
for (int k_ = 1; k_ < sz; k_++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
bin2[i][j][k_] = f;
g[f].resize(X);
for (int x = 0; x < X; x++)
{
g[f][x] = bin2[min(i + y * x, n - 1)][j][k_ - 1];
}
f++;
}
}
y *= X;
}
y /= X;
deep.resize(g.size() ,inf);
vector <vector < int>> q(2);
for (int i = 0; i < 2; i++)
q[i].resize(n * m + 2);
int f1_ = 0;
int f2_ = 0;
q[0][0] = bin[i_st][j_st][0];
f1_ = 1;
deep[bin[i_st][j_st][0]] = 0;
vector <pair <int, int>> go;
go.push_back({ 1 , 0 });
go.push_back({ -1 , 0 });
go.push_back({ 0 , 1 });
go.push_back({ 0 , -1 });
for (int d = 0 ; d < n*m+1 ; d ^= 1)
{
if (f1_ == 0)
break;
for (int ind = 0; ind < f1_; ind++)
{
int ind__ = q[d][ind];
if (ind__ < f2)
{
int i_ = vp[ind__].first;
int j_ = vp[ind__].second;
for (int i = 0; i < 4; i++)
{
int i__ = i_ + go[i].first;
int j__ = j_ + go[i].second;
if ((i__ >= 0) and (i__ < n))
{
if ((j__ >= 0) and (j__ < m))
{
if (deep[bin[i__][j__][0]] > d)
{
if (vs[i__][j__] == '.')
{
deep[bin[i__][j__][0]] = d;
q[d][f1_] = bin[i__][j__][0];
f1_++;
}
}
}
}
}
}
else
{
for (int i = 0; i < g[ind__].size(); i++)
{
int ind_s = g[ind__][i];
if (deep[ind_s] > d)
{
deep[ind_s] = d;
q[d][f1_] = ind_s;
f1_++;
}
}
}
}
for (int ind = 0; ind < f1_; ind++)
{
int ind__ = q[d][ind];
if (ind__ < f2)
{
int i_ = vp[ind__].first;
int j_ = vp[ind__].second;
if (i_ >= k)
{
int l = j_ - (k - 1);
int r = j_ + (k - 1);
l = max(l, 0);
r = min(r, m - 1);
int i__ = i_ - k;
int j__ = l;
int lenth = r - l + 1;
int c = 0;
int x = 1;
while (x * X <= lenth)
{
x *= X;
c++;
}
for (int c_ = 0; c_ < (lenth / x); c_++)
{
if (deep[bin[i__][j__ + (c_ * x)][c]] == inf)
{
deep[bin[i__][j__ + (c_ * x)][c]] = d + 1;
q[d ^ 1][f2_] = bin[i__][j__ + (c_ * x)][c];
f2_++;
//q[d + 1].push_back(bin[i__][j__ + (c_ * x)][c]);
}
}
if (deep[bin[i__][r - x + 1][c]] == inf)
{
deep[bin[i__][r - x + 1][c]] = d + 1;
q[d ^ 1][f2_] = bin[i__][r - x + 1][c];
f2_++;
//q[d + 1].push_back(bin[i__][r - x + 1][c]);
}
//q[d + 1].push_back(bin[i__][r - x+1][c]);
}
if (i_+ k < n)
{
int l = j_ - (k - 1);
int r = j_ + (k - 1);
l = max(l, 0);
r = min(r, m - 1);
int i__ = i_ + k;
int j__ = l;
int lenth = r - l + 1;
int c = 0;
int x = 1;
while (x * X <= lenth)
{
x *= X;
c++;
}
for (int c_ = 0; c_ < (lenth / x); c_++)
{
if (deep[bin[i__][j__ + (c_ * x)][c]] == inf)
{
deep[bin[i__][j__ + (c_ * x)][c]] = d + 1;
q[d ^ 1][f2_] = bin[i__][j__ + (c_ * x)][c];
f2_++;
//q[d + 1].push_back(bin[i__][j__ + (c_ * x)][c]);
}
}
if (deep[bin[i__][r - x + 1][c]] == inf)
{
deep[bin[i__][r - x + 1][c]] = d + 1;
q[d ^ 1][f2_] = bin[i__][r - x + 1][c];
f2_++;
//q[d + 1].push_back(bin[i__][r - x + 1][c]);
}
//q[d + 1].push_back(bin[i__][r - x+1][c]);
}
if (j_ >= k)
{
int l = i_ - (k - 1);
int r = i_ + (k - 1);
l = max(l, 0);
r = min(r, n - 1);
int i__ = l;
int j__ = j_ - k;
int lenth = r - l + 1;
int c = 0;
int x = 1;
while (x * X <= lenth)
{
x *= X;
c++;
}
for (int c_ = 0; c_ < (lenth / x); c_++)
{
if (deep[bin2[i__ + (c_ * x)][j__][c]] > d + 1)
{
deep[bin2[i__ + (c_ * x)][j__][c]] = d + 1;
//q[d + 1].push_back(bin2[i__ + (c_ * x)][j__][c]);
q[d ^ 1][f2_] = bin2[i__ + (c_ * x)][j__][c];
f2_++;
}
}
if (deep[bin2[r - x + 1][j__][c]] > d + 1)
{
deep[bin2[r - x + 1][j__][c]] = d + 1;
//q[d + 1].push_back(bin2[r - x + 1][j__][c]);
q[d ^ 1][f2_] = bin2[r - x + 1][j__][c];
f2_++;
}
//q[d + 1].push_back(bin[l - x+1][j__][c]);
}
if (j_+k < m)
{
int l = i_ - (k - 1);
int r = i_ + (k - 1);
l = max(l, 0);
r = min(r, n - 1);
int i__ = l;
int j__ = j_ + k;
int lenth = r - l + 1;
int c = 0;
int x = 1;
while (x * X <= lenth)
{
x *= X;
c++;
}
for (int c_ = 0; c_ < (lenth / x); c_++)
{
if (deep[bin2[i__ + (c_ * x)][j__][c]] > d + 1)
{
deep[bin2[i__ + (c_ * x)][j__][c]] = d + 1;
//q[d + 1].push_back(bin2[i__ + (c_ * x)][j__][c]);
q[d ^ 1][f2_] = bin2[i__ + (c_ * x)][j__][c];
f2_++;
}
}
if (deep[bin2[r - x + 1][j__][c]] > d + 1)
{
deep[bin2[r - x + 1][j__][c]] = d + 1;
//q[d + 1].push_back(bin2[r - x + 1][j__][c]);
q[d ^ 1][f2_] = bin2[r - x + 1][j__][c];
f2_++;
}
//q[d + 1].push_back(bin[l - x+1][j__][c]);
}
}
}
for (int i = 0; i < f2_; i++)
{
q[d][i] = q[d ^ 1][i];
}
f1_ = f2_;
f2_ = 0;
}
//cout << deep[i_f][j_f] << "\n";
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (abs(i - i_f) <= k)
{
if (abs(j - j_f) <= k)
{
if ((abs(i - i_f) + abs(j - j_f)) != 2 * k)
{
deep[bin[i_f][j_f][0]] = min(deep[bin[i_f][j_f][0]], deep[bin[i][j][0]] + 1);
}
}
}
}
}
cout << deep[bin[i_f][j_f][0]];
}
/*
5 5 2
2 2
4 4
#....
#.##.
####.
##...
.....
*/
Compilation message
Main.cpp:1: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
1 | #pragma target("arch=icelake-server")
|
Main.cpp: In function 'int main()':
Main.cpp:253:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
253 | for (int i = 0; i < g[ind__].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
