Language: C++

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
//typedef tree<int,null_type,less<int >,rb_tree_tag,tree_order_statistics_node_update>indexed_set;
template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p);
template <class T>
ostream &operator <<(ostream &os, vector<T>&v);
template <class T>
ostream &operator <<(ostream &os, multiset<T>&v);
template <class T1, class T2>
ostream &operator <<(ostream &os, map<T1,T2>&v);
#ifndef ONLINE_JUDGE
#define debug(a) cout<<#a<<" --> "<<(a)<<"\n";
#define debug2(a) cout<<#a<<" --> "<<(a)<<" ";
#define HERE cout<<"here - "<<__LINE__<<"\n";
#else
#define debug(a)
#define debug2(a)
#define HERE
#endif
const ll mod = 998244353  ;
const int N = 2e5+5;
typedef pair<int,int> pii;
int h,w,k;
int x1,y1,x2,y2;
vector<string>s;
vector<pii>dir ={ {-1,0},{1,0},{0,1},{0,-1}  };
bool issafe(int i, int j)
{
    return i>=0 && j>=0 && i<h && j<w;
}
vector<pii>path;

bool bfs()
{
    vector<vector<bool> >vis(h,vector<bool>(w,false));
    vector<vector<pii> >parent(h,vector<pii>(w,{-1,-1}));
    queue<pii>q;
    vis[x1][y1]= true;
    q.push({x1,y1});
    while(!q.empty())
    {
        pii p = q.front();
        q.pop();
        if(parent[p.first][p.second]== make_pair(-1,-1))
        {

        }
        else{
            pii bal =  parent[p.first][p.second];
//            pii d = {p.first-bal.first , p.second- bal.second };
//            debug(p);
//            debug(bal);
//            debug(p.first-bal.first);
//            debug(p.second- bal.second);
//            debug(d);

            int x = p.first + p.first-bal.first;
            int y = p.second + p.second- bal.second;
            if(issafe(x,y) &&vis[x][y]==false&& s[x][y]=='.')
            {
                vis[x][y]= true;
                q.push({x,y});
                parent[x][y] = p;
            }
        }
        for(pii it:dir)
        {
            int x = p.first + it.first;
            int y = p.second + it.second;
            if(issafe(x,y) &&vis[x][y]==false&& s[x][y]=='.')
            {
                vis[x][y]= true;
                q.push({x,y});
                parent[x][y] = p;
            }
        }
    }
    if(vis[x2][y2]== false)
        return false;

    pii now = {x2,y2};
    while(now!= make_pair(x1,y1))
    {
        path.push_back(now);
        now = parent[now.first][now.second];
    }
    path.push_back({x1,y1});
    reverse(path.begin(),path.end());
    //debug(path);
    return true;

}
bool fun(pii dd , int i)
{
    pii d = {path[i-1].first - path[i].first,path[i-1].second - path[i].second};
    return (d.first==dd.first)&&(d.second==dd.second);
}
void TEST_CASES(int cas)
{
    scanf("%d %d %d",&h,&w,&k);
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    x1--;
    y1--;
    x2--;
    y2--;
    s.resize(h);
    for(int i=0;i<h;i++)
    {
        cin>>s[i];
    }
    if(bfs()==false)
    {
        printf("-1\n");
        return;
    }
    int ans =0;
    for(int i=1;i<path.size();)
    {
        int cnt =0;
        pii d = {path[i-1].first - path[i].first,path[i-1].second - path[i].second};
        while(i<path.size()&& fun(d,i))
        {
            i++;
            cnt++;
        }
        //debug(cnt);
        ans+= (cnt/k);
        if(cnt%k)
            ans++;
    }
    printf("%d\n",ans);
}


/*

*/

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int t=1,cas=0;
    //scanf("%d",&t);
    while(t--)
    {
        TEST_CASES(++cas);
    }

    return 0;
}



//os.order_of_key(v): returns how many elements strictly less than v
//os.find_by_order()

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p)
{
    os<<"{"<<p.first+1<<", "<<p.second+1<<"} ";
    return os;
}
template <class T>
ostream &operator <<(ostream &os, vector<T>&v)
{
    os<<"[ ";
    for(int i=0; i<v.size(); i++)
    {
        os<<v[i]<<" " ;
    }
    os<<" ]";
    return os;
}

template <class T>
ostream &operator <<(ostream &os, multiset<T>&v)
{
    os<<"[ ";
    for(T i:v)
    {
        os<<i<<" ";
    }
    os<<" ]";
    return os;
}
template <class T1, class T2>
ostream &operator <<(ostream &os, map<T1,T2>&v)
{
    for(auto i:v)
    {
        os<<"Key : "<<i.first<<" , Value : "<<i.second<<endl;
    }
    return os;
}


Compiler output:
a.cc:29:8: error: 'int y1' redeclared as different kind of entity
   29 | int x1,y1,x2,y2;
      |        ^~
In file included from /usr/include/features.h:523,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/c++config.h:683,
                 from /usr/include/c++/14/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:33,
                 from a.cc:1:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:257:1: note: previous declaration 'double y1(double)'
  257 | __MATHCALL (y1,, (_Mdouble_));
      | ^~~~~~~~~~
a.cc: In function 'bool bfs()':
a.cc:43:13: error: invalid conversion from 'double (*)(double) noexcept' to 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-fpermissive]
   43 |     vis[x1][y1]= true;
      |             ^~
      |             |
      |             double (*)(double) noexcept
In file included from /usr/include/c++/14/vector:67,
                 from /usr/include/c++/14/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:53:
/usr/include/c++/14/bits/stl_bvector.h:1086:28: note:   initializing argument 1 of 'std::vector<bool, _Alloc>::reference std::vector<bool, _Alloc>::operator[](size_type) [with _Alloc = std::allocator<bool>; reference = std::vector<bool>::reference; size_type = long unsigned int]'
 1086 |       operator[](size_type __n)
      |                  ~~~~~~~~~~^~~
a.cc:44:11: error: no matching function for call to 'std::queue<std::pair<int, int> >::push(<brace-enclosed initializer list>)'
   44 |     q.push({x1,y1});
      |     ~~~~~~^~~~~~~~~
In file included from /usr/include/c++/14/queue:66,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:157:
/usr/include/c++/14/bits/stl_queue.h:283:7: note: candidate: 'void std::queue<_Tp, _Sequence>::push(const value_type&) [with _Tp = std::pair<int, int>; _Sequence = std::deque<std::pair<int, int>, std::allocator<std::pair<int, int> > >; value_type = std::pair<int, int>]'
  283 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/14/bits/stl_queue.h:283:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const std::queue<std::pair<int, int> >::value_type&' {aka 'const std::pair<int, int>&'}
  283 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/stl_queue.h:288:7: note: candidate: 'void std::queue<_Tp, _Sequence>::push(value_type&&) [with _Tp = std::pair<int, int>; _Sequence = std::deque<std::pair<int, int>, std::allocator<std::pair<int, int> > >; value_type = std::pair<int, int>]'
  288 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/14/bits/stl_queue.h:288:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::queue<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
  288 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~
a.cc:87:14: error: no match for 'operator!=' (operand types are 'pii' {aka 'std::pair<int, int>'} and 'std::pair<int, double (*)(double) noexcept>')
   87 |     while(now!= make_pair(x1,y1))
      |           ~~~^~ ~~~~~~~~~~~~~~~~
      |           |              |
      |           |              pair<[...],double (*)(double) noexcept>
      |           pair<[...],int>
In file included from /usr/include/c++/14/regex:68,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:181:
/usr/include/c++/14/bits/regex.h:1132:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator!=(const sub_match<_BiIter>&, const sub_match<_BiIter>&)'
 1132 |     operator!=(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1132:5: note:   template argument deduction/substitution failed:
a.cc:87:32: note:   'pii' {aka 'std::pair<int, int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   87 |     while(now!= make_pair(x1,y1))
      |                                ^
/usr/include/c++/14/bits/regex.h:1212:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator!=(__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const sub_match<_BiIter>&)'
 1212 |     operator!=(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1212:5: note:   template argument deduction/substitution failed:
a.cc:87:32: note:   'pii' {aka 'std::pair<int, int>'} is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
   87 |     while(now!= make_pair(x1,y1))
      |                                ^
/usr/include/c++/14/bits/regex.h:1305:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator!=(const sub_match<_BiIter>&, __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1305 |     operator!=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1305:5: note:   template argument deduction/substitution failed:
a.cc:87:32: note:   'pii' {aka 'std::pair<int, int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   87 |     while(now!= make_pair(x1,y1))
      |                                ^
/usr/include/c++/14/bits/regex.h:1379:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator!=(const typename std::iterator_traits<_Iter>::value_type*, const sub_match<_BiIter>&)'
 1379 |     operator!=(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1379:5: note:   template argument deduction/substitution failed:
a.cc:87:32: note:   'std::pair<int, double (*)(double) noexcept>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   87 |     while(now!= make_pair(x1,y1))
      |                                ^
/usr/include/c++/14/bits/regex.h:1473:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator!=(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1473 |     operator!=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1473:5: note:   template argument deduction/substitution failed:
a.cc:87:32: note:   'pii' {aka 'std::pair<int, int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   87 |     while(now!= make_pair(x1,y1))
      |                                ^
/usr/include/c++/14/bits/regex.h:1547:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator!=(const typename std::iterator_traits<_Iter>::value_type&, const sub_match<_BiIter>&)'
 1547 |     operator!=(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1547:5: note:   template argument deduction/substitution failed:
a.cc:87:32: note:   'std::pair<int, double (*)(double) noexcept>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   87 |     while(now!= make_pair(x1,y1))
      |                                ^
/usr/include/c++/14/bits/regex.h:1647:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator!=(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1647 |     operator!=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1647:5: note:   template argument deduction/substitution failed:
a.cc:87:32: note:   'pii' {aka 'std::pair<int, int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   87 |     while(now!= make_pair(x1,y1))
      |                                ^
/usr/include/c++/14/bits/regex.h:2213:5: note: candidate: 'template<class _Bi_iter, class _Alloc> bool std::__cxx11::operator!=(const match_results<_BiIter, _Alloc>&, const match_results<_BiIter, _Alloc>&)'
 2213 |     operator!=(const match_results<_Bi_iter, _Alloc>& __m1,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:2213:5: note:   template argument deduction/substitution failed:
a.cc:87:32: note:   'pii' {aka 'std::pair<int, int>'} is not derived from 'const std::__cxx11::match_results<_BiIter, _Alloc>'
   87 |     while(now!= make_pair(x1,y1))
      |                                ^
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51:
/usr/include/c++/14/bits/stl_pair.h:1052:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator!=(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
 1052 |     operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1052:5: note:   template argument deduction/substitution failed:
a.cc:87:32: note:   deduced conflicting types for parameter '_T2' ('int' and 'double (*)(double) noexcept')
   87 |     while(now!= make_pair(x1,y1))
      |                                ^
In file included from /usr/include/c++/14/bits/stl_algobase.h:67:
/usr/include/c++/14/bits/stl_iterator.h:455:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator!=(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  455 |     operator!=(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:455:5: note:   template argument deduction/substitution failed:
a.cc:87:32: note:   'pii' {aka 'std::pair<int, int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
   87 |     while(now!= make_pair(x1,y1))
      |                                ^
/usr/include/c++/14/bits/stl_iterator.h:500:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator!=(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  500 |     operator!=(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:500:5: note:   template argument deduction/substitution failed:
a.cc:87:32: note:   'pii' {aka 'std::pair<int, int>'} is no