#include<bits/stdc++.h>
using namespace std;
const int N = 6e6;
const int inf = 2e9;
int k,n,m,sx,sy,ex,ey;
int d[8][2] = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int ans = inf;
cin>>n>>m>>k;
cin>>sx>>sy>>ex>>ey;
vector<vector <char>> v(n + 2,vector<char>(m + 2,0));
vector<vector <vector<bool>>> vis(n + 2,vector<vector<bool>>(m + 2,vector<bool>(2,0)));
vector <array<int,2>> q;
vector <array<int,3>> q2;
for(int i = 0;i < n + 2;i++){
v[i][0] = 2;
v[i][m + 1] = 2;
}
for(int i = 0;i < m + 2;i++){
v[0][i] = 2;
v[n + 1][i] = 2;
}
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
char ch;
cin>>ch;
if(ch == '.'){
v[i + 1][j + 1] = 0;
}else{
v[i + 1][j + 1] = 1;
}
}
}
vis[sx][sy][0] = 1;
q.push_back({sx,sy});
for(int i = 0;i <= n + m;i++){
int pt = 0;
q2.clear();
while(pt < q.size()){
auto x = q[pt];pt++;
if(x[0] == ex && x[1] == ey){
ans = i;
}
///bfs
if(!vis[x[0]][x[1]][1]){
q2.push_back({x[0],x[1],0});
}
for(int j = 0;j < 4;j++){
int nx = x[0] + d[j][0];
int ny = x[1] + d[j][1];
if(!vis[nx][ny][0] && v[nx][ny] == 0){
vis[nx][ny][0] = 1;
q.push_back({nx,ny});
}
}
}
q.clear();
pt = 0;
while(pt < q2.size()){
auto x = q2[pt];
pt++;
if(!vis[x[0]][x[1]][0]){
q.push_back({x[0],x[1]});
vis[x[0]][x[1]][0] = 1;
}
if(x[2] != k - 1){
for(int j = 0;j < 8;j++){
int nx = x[0] + d[j][0];
int ny = x[1] + d[j][1];
if(!vis[nx][ny][1] && v[nx][ny] != 2){
vis[nx][ny][1] = 1;
q2.push_back({nx,ny,x[2] + 1});
}
}
}else{
for(int j = 0;j < 4;j++){
int nx = x[0] + d[j][0];
int ny = x[1] + d[j][1];
if(!vis[nx][ny][0] && v[nx][ny] != 2){
vis[nx][ny][0] = 1;
q.push_back({nx,ny});
}
}
}
}
}
assert(pt + pt2 <= 2*N);
cout<<ans<<'\n';
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | while(pt < q.size()){
| ~~~^~~~~~~~~~
Main.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | while(pt < q2.size()){
| ~~~^~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from Main.cpp:1:
Main.cpp:89:12: error: 'pt' was not declared in this scope
89 | assert(pt + pt2 <= 2*N);
| ^~
Main.cpp:89:17: error: 'pt2' was not declared in this scope
89 | assert(pt + pt2 <= 2*N);
| ^~~
