第3题 步数(原始) 查看测评数据信息
有一个二维网格，从上往下，行的编号从1至n，从左往右，列的编号是1至m。
第i行第j列的格子编号为(i,j)，如果 a[i][j]为 '@',表示格子(i,j)有障碍物，
如果a[i][j]为'.'则表示格子(i,j)可通行。
奶牛bessie当前在 格子(r1,c1)，它每一步可以选择往上、下、左、右四个方向之一走 1 至k 格，也就是每一步至少走1格，最多可以走k格。
任何时刻都不能进入障碍物格子，也不能走到网格外面，不能走出界。
问你最少需要多少步才能走到 格子(r2,c2) ，如果不能走到，输出 −1 。
输入格式
第一行，n,m,k。 1<=n,m,k<=1000000, n*m <= 1000000。
第二行，r1, c1, r2, c2。 1<=r1,r2<=n, 1<=c1,c2<=m。
接下来是n行m列的二维网格a[1..n][1..m]，其中a[i][j]是'@'或'.'。
【提示】
本题测试点数据较大，只有约10%的数据满足n*m<=100
输出格式
一个整数。
输入/输出例子1
输入：
3 5 2
3 2 3 4
.....
.@..@
..@..
输出：
5
输入/输出例子2
输入：
1 6 4
1 1 1 6
......
输出：
2
样例解释
无
分析
和普通广搜没什么区别，就是最短路了，唯一也就是每一步至少走1格，最多可以走k格。
这题毕竟恶心的是数组范围，卡了很久，最终还是开主函数里面了，根据nm的值来定，不开固定的了
同时注意一下剪枝，别超时了，附讲解时的图
同时，不能用vis来剪走过的路，因为可能确定了值但不是最小值！
还有注意起点就是‘@’的情况
#include <bits/stdc++.h>
using namespace std;
const int N=6005;
const int dx[]={-1, 0, 0, 1}, dy[]={0, -1, 1, 0};
struct point
{
int x, y;
};
long long n, m, k, r1, c1, r2, c2;
queue<point> q;
int main()
{
scanf("%lld%lld%lld", &n, &m, &k);
scanf("%lld%lld%lld%lld", &r1, &c1, &r2, &c2);
char mp[n+5][m+5]; //注意！！
long long dis[n+5][m+5];
for (int i=1; i<=n; i++)
scanf("%s", mp[i]+1);
if (mp[r1][c1]=='@') //注意！
{
printf("-1");
return 0;
}
int x=r1, y=c1;
q.push({x, y});
memset(dis, 63, sizeof dis);
dis[x][y]=0;
while (!q.empty())
{
point t=q.front();
q.pop();
//vis[t.x][t.y]=0;
for (int j=0; j<4; j++)
{
for (int i=1; i<=k; i++)
{
int nx=t.x+dx[j]*i, ny=t.y+dy[j]*i; //*i相当于调整走1~k步
if (nx<1 || nx>n || ny<1 || ny>m) break;
if (mp[nx][ny]=='@') break;
if (dis[t.x][t.y]+1>dis[nx][ny]) break;
//if (vis[nx][ny]) break;
if (dis[nx][ny]>dis[t.x][t.y]+1)
{
dis[nx][ny]=dis[t.x][t.y]+1;
q.push({nx, ny});
}
//vis[nx][ny]=1;
}
}
}
/*for (int i=1; i<=n; i++)
{
for (int j=1; j<=m; j++)
cout<<dis[i][j]<<" ";
cout<<endl;
}*/
if (dis[r2][c2]==dis[0][0]) printf("-1");
else printf("%lld", dis[r2][c2]);
return 0;
}
/*
5 6 4
1 1 2 4
......
.@@.@@
.....@
..@@.@
@....@
*/