Olya loves energy drinks. She loves them so much that her room is full of empty cans from energy drinks.
Formally, her room can be represented as a field of n?×?m cells, each cell of which is empty or littered with cans.
Olya drank a lot of energy drink, so now she can run k meters per second. Each second she chooses one of the four directions (up, down, left or right) and runs from 1 to k meters in this direction. Of course, she can only run through empty cells.
Now Olya needs to get from cell (x1,?y1) to cell (x2,?y2). How many seconds will it take her if she moves optimally?
It's guaranteed that cells (x1,?y1) and (x2,?y2) are empty. These cells can coincide.
InputThe first line contains three integers n, m and k (1?≤?n,?m,?k?≤?1000) — the sizes of the room and Olya's speed.
Then n lines follow containing m characters each, the i-th of them contains on j-th position "#", if the cell (i,?j) is littered with cans, and "." otherwise.
The last line contains four integers x1,?y1,?x2,?y2 (1?≤?x1,?x2?≤?n, 1?≤?y1,?y2?≤?m) — the coordinates of the first and the last cells.
OutputPrint a single integer — the minimum time it will take Olya to get from (x1,?y1) to (x2,?y2).
If it's impossible to get from (x1,?y1) to (x2,?y2), print -1.
Examples3 4 4
....
###.
....
1 1 3 1
3
3 4 1
....
###.
....
1 1 3 1
8
2 2 1
.#
#.
1 1 2 2
-1
In the first sample Olya should run 3 meters to the right in the first second, 2 meters down in the second second and 3 meters to the left in the third second.
In second sample Olya should run to the right for 3 seconds, then down for 2 seconds and then to the left for 3 seconds.
#include<cstring>
#include<queue>//int gcd(int a,int b){return b?gcd(b,a%b):a;}
#include<cstdio>
#define ll long long
#define maxn 1001
#define INF 100000000
using namespace std;struct node
{int x,y,t;node(int xx=0,int yy=0,int tt=0){x=xx;y=yy;t=tt;}
};char mp[maxn][maxn];
int n,m,k;
int sx,sy,ex,ey;int dir1[]={0,-1,0,1};
int dir2[]={1,0,-1,0};
int vis[maxn][maxn];
int dist[maxn][maxn];///内存初始空间inline bool judge(int x,int y)
{if(x<0||x>=n) return false;if(y<0||y>=m) return false;return true;
}
/*
本身感觉就是一个简单的BFS问题没想到还有那么多。。。。玄学。。
现在还不知道哪里错了。。。基本思路我想大概都一样吧，，，标记走没走过是一方面，，，
除此之外还要记录其最短路并通过这个筛选
*/inline void BFS()
{queue<node> q;q.push( node(sx,sy) );vis[sx][sy]=(1<<4)-1;dist[sx][sy]=0;while( !q.empty() ){node tmp=q.front();q.pop();if( tmp.x==ex && tmp.y==ey ) return ;for(int j=0;j<4;j++)for(int i=1;i<=k;i++){int tx=tmp.x+i*dir1[j];int ty=tmp.y+i*dir2[j];if( !judge(tx,ty) || mp[tx][ty]=='#' ) break;if( vis[tx][ty] & (1<<i) ) break;int flag=0;if(!vis[tx][ty]) flag=1;vis[tx][ty] |= 1<<i;if(flag){dist[tx][ty]=dist[tmp.x][tmp.y]+1;q.push( node(tx,ty,tmp.t+1) );}}}
}int main()
{char c;scanf("%d%d%d",&n,&m,&k);for(int i=0;i<n;i++) scanf("%s",mp[i]);scanf("%d%d%d%d",&sx,&sy,&ex,&ey);sx--,sy--,ex--,ey--;BFS();if(dist[ex][ey]==INF) puts("-1");else printf("%d\n",dist[ex][ey]);return 0;
}