0AB路线 - 蓝桥云课 (lanqiao.cn)

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,m,k;
//存迷宫格子
char board[1005][1005];
//vis[i][j][k]存坐标(i,j)的格子，在一个周期中第k次经过它
bool vis[1005][1005][15];
//移动的向量
int move_hang[4]={0,1,0,-1},move_lie[4]={1,0,-1,0};
struct Node{
	int x;//坐标
	int y;
	int cnt;//当前第几步了
};
int bfs(){
	queue<Node> q;
	q.push({0,0,1});
	vis[0][0][1]=true;
	while(q.size()){
		auto t=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int xx=t.x+move_hang[i],yy=t.y+move_lie[i];
			if(xx<0||yy<0||xx>=n||yy>=m) continue;//保证下标不越界
			if(vis[xx][yy][(t.cnt+1+k-1)%k+1]) continue;//保证不重复，第三维的算法自己画个图模拟模拟就知道什么意思了
			int p=(t.cnt+1+k-1)/k%2;//自己画个图模拟模拟就知道什么意思了
			//p为1 该步应该走A
			if(p==1){
				if(board[xx][yy]!='A') continue;
				else{
					q.push({xx,yy,t.cnt+1});
					vis[xx][yy][(t.cnt+1+k-1)%k+1]=true;
				}
			}
			//p为2 该步应该走B
			else{
				if(board[xx][yy]!='B') continue;
				else{
					q.push({xx,yy,t.cnt+1});
					vis[xx][yy][(t.cnt+1+k-1)%k+1]=true;
				}
			}
//			cout<<xx<<" "<<yy<<endl;
			if(xx==n-1&&yy==m-1){//走到迷宫右下角
				return t.cnt;
			}
		}
	}
	return -1;
}
void solve(){
	cin>>n>>m>>k;
	for(int i=0;i<n;i++){
		string str;
		cin>>str;
		for(int j=0;j<m;j++){
			board[i][j]=str[j];
		}
	}
	cout<<bfs();
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0;
}