一、题目
点此看题
二、解法
考察搜索的优化，我们把访问标记设置成每个位置是从哪个方向来的，而不能直接标记，这是为了使
那部分的移动是连续的（一旦访问过就不用再做了，这样每个位置只能被访问一次），考虑下图：
如此图，他们在
的同一层，假设红先访问并标记，如果我们的标记不考虑方向那么就不满足上述的性质。
#include <cstdio>
#include <queue>
using namespace std;
const int M = 1005;
int read()
{int x=0,f=1;char c;while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
int n,m,k,sx,sy,tox,toy,dx[4]={1,-1},dy[4]={0,0,1,-1};
char a[M][M];bool vis[M][M][4];
struct node
{int x,y,d;
};
void bfs()
{queue<node> q;vis[sx][sy][0]=vis[sx][sy][1]=vis[sx][sy][2]=vis[sx][sy][2]=1;q.push(node{sx,sy,0});while(!q.empty()){node t=q.front();q.pop();if(t.x==tox && t.y==toy){printf("%d\n",t.d);return ;}for(int i=0;i<=3;i++)for(int j=1;j<=k;j++){int tx=t.x+dx[i]*j,ty=t.y+dy[i]*j;if(tx<1 || tx>n || ty<1 || ty>m) break;if(a[tx][ty]=='#' || vis[tx][ty][i]) break;vis[tx][ty][i]=1;q.push(node{tx,ty,t.d+1}); }}puts("-1");
}
signed main()
{n=read();m=read();k=read();for(int i=1;i<=n;i++)scanf("%s",a[i]+1);sx=read();sy=read();tox=read();toy=read();bfs();
}