第3题 步数有一个二维网格，从上往下，行的编号从1至n，从左往右，列的编号是1至m。第i行第j列的格子编号为(i,j)，如果a[i][j]为 '@',表示格子(i,j)有障碍物，如

第3题 步数X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
有一个二维网格，从上往下，行的编号从1至n，从左往右，列的编号是1至m。X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第i行第j列的格子编号为(i,j)，如果a[i][j]为 '@',表示格子(i,j)有障碍物，X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
如果a[i][j]为'.'则表示格子(i,j)可通行。X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
奶牛bessie当前在格子(r1,c1)，它每一步可以选择往上、下、左、右四个方向之一走 1 至k 格，也就是每一步至少走1格，最多可以走k格。X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
任何时刻都不能进入障碍物格子，也不能走到网格外面，不能走出界。X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
问你最少需要多少步才能走到格子(r2,c2) ，如果不能走到，输出 −1 。X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入格式X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第一行，n,m,k。 1<=n,m,k<=1000000, n*m <= 1000000。X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第二行，r1, c1, r2, c2。 1<=r1,r2<=n, 1<=c1,c2<=m。X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
接下来是n行m列的二维网格a[1..n][1..m]，其中a[i][j]是'@'或'.'。X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【提示】X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
本题测试点数据较大，只有约10%的数据满足n*m<=100X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出格式X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
一个整数。X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入/输出例子1X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入：X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3 5 2X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3 2 3 4X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
.....X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
.@..@X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
..@..X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出：X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入/输出例子2X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入：X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 6 4X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 1 1 6X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
......X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出：X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2X4X100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库