~~应该能过官方数据吧~~
---
回归正题。我开始想过更简单的深搜，但是我怕无法记忆化，所以选择了广搜。和普通的广搜不同，此题的队列要存 $3$ 个维度，分别是 $x$，$y$，$z$，分别表示横坐标、纵坐标、目前的步数模 $2k$ 的值。
此时我们可以把每 $2k$ 步进行分组，前 $k$ 步走在 ```A``` 的格子上，后 $k$ 步走在 ```B``` 的格子上。
这里的每一步都要分类讨论，以下记 $a$ 为下一步模 $2k$ 的值。
- 当 $a \ge k$ 时，下一步必须走在 ```B``` 的格子上。
- 否则，下一步必须走在 ```A``` 的格子上。
然后就做完了。
#include<bits/stdc++.h> using namespace std; const int N=1005; int n,m,k,x,y,z,nx,ny,nz; int dis[N][N]; char mp[N][N]; int dx[]={-1,1,0,0}; int dy[]={0,0,-1,1}; queue< pair< pair<int,int> ,int> >q; //用queue记三维信息 int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=1; i<=n; i++) scanf("%s",mp[i]+1); if(mp[1][1]!='A'){ puts("-1"); return 0; } memset(dis,0x3f,sizeof dis); dis[1][1]=0; q.push({{1,1},0}); while(!q.empty()){ x=q.front().first.first; y=q.front().first.second; z=q.front().second; q.pop(); for(int i=0; i<4; i++){ nx=x+dx[i],ny=y+dy[i],nz=(z+1)%(2*k); if(nx<1 || nx>n || ny<1 || ny>m) continue; if(nz<k && mp[nx][ny]=='B') continue; if(nz>=k && mp[nx][ny]=='A') continue; if(dis[nx][ny]>dis[x][y]+1){ dis[nx][ny]=dis[x][y]+1; q.push({{nx,ny},nz}); } } } if(dis[n][m]==dis[0][0]) puts("-1"); else printf("%d\n",dis[n][m]); return 0; }