题目
Snuke，水上平衡车，住在一个矩形池塘，可以看成 H 列 W 行，(i, j) 表示第 i 列第 j 行。池塘里长着荷叶，荷叶是不能进入的。如果 cij 是 @，表示荷叶。如果 cij 是 .，表示不是荷叶。
Snuke 每次可以向北、东、南、西的任意同一个方向移动1 ～ K 步，但是不能通过荷叶，同时也不能移动到池塘外。
给我们起点坐标 (x1, y1) 和终点坐标 (x2, y2)，要求我们找到最小的移动次数。如果不能到达，输出 -1。
\(1 ≤ H,W,K ≤ 10^6\)
\(H × W ≤ 10^6\)
题目分析
对于数据分析，可以把矩阵转化为一条链，而链的长度不会超过\(1e6\)，这样解决了矩阵的访问
考虑对整个问题BFS，对答案记忆化，实际上每一个格子都会被访问多次，但在BFS拓展时会有操作4*k次，于是需要对BFS剪枝
首先，如果超出边界便不用走完k步
如果当前到达的步数会大于目前格子的最小步数，说明，接下的步数，都可以用格子的最小步数+1所替换，怎样都比现在的优，所以可以break
如果当前到达的步数会等于目前格子的最小步数，那这一步就没有走的必要，但当前格子的步数可能为另一条路转移，所以k步要继续走
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int n,m,k;
int mp[MAXN];
char s[MAXN];int sx,sy,tx,ty;
int get(int x,int y)
{
return (x-1)*m+y;
}
struct node{
int x,y;
int step;
};
int zfx[5]={0,0,1,-1};
int zfy[5]={1,-1,0,0};
int vis[MAXN];
int Bfs()
{
memset(vis,0x3f,sizeof(vis));
queue<node>q;
node nowx;
nowx.step=0;
nowx.x=sx;
nowx.y=sy;
vis[get(nowx.x,nowx.y)]=0;
q.push(nowx);
while(q.size())
{
node temp=q.front();
q.pop();
if(temp.x==tx&&temp.y==ty)
{
return temp.step;
}
for(int j=0;j<4;j++)
{
for(int i=1;i<=k;i++)
{
int nowxs=temp.x+i*zfx[j];
int nowys=temp.y+i*zfy[j];
if(nowxs>n||nowys>m||nowxs<1||nowys<1)
{
break;
}
if(mp[get(nowxs,nowys)])
{
break;
}
node now;
now.x=nowxs;
now.y=nowys;
now.step=temp.step+1;
if(now.step>vis[get(now.x,now.y)])
{
break;
}
if(now.step==vis[get(now.x,now.y)])
{
continue;
}
vis[get(now.x,now.y)]=now.step;
q.push(now);
}
}
}
return -1;
}
int main()
{
scanf("%d %d %d",&n,&m,&k);
scanf("%d %d %d %d",&sx,&sy,&tx,&ty);
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
for(int j=1;j<=m;j++)
{
if(s[j]==‘@‘)
{
mp[get(i,j)]=1;
}
}
}
printf("%d",Bfs());
}