蓝桥14届国赛b组AB路线

一道比较特殊的bfs，被访问的位置仍然可以继续访问，只有走的位置相同且到这个位置的步数相同，搜索结果才会相同

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define de(id,x) cout<<id<<" "<<#x<<" = "<<x<<" ";
#define deg(id,x) cout<<id<<" "<<#x<<" = "<<x<<endl;
using namespace std;
const int mod=998244353;
typedef pair<int,int> PII;
const int N=1010;
int n,m,k;
char g[N][N];
int dist[N][N][11];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
struct point
{
    int x,y,cnt;
};
void bfs()
{
    queue<point> q;
    if(g[1][1]=='A')
    {
      q.push({1,1,1});
      dist[1][1][1]=0; 
    }
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        //cout<<t.x<<" "<<t.y<<endl;
        for(int i=0;i<4;i++)
        {
            int xx=t.x+dx[i],yy=t.y+dy[i];
            if(xx<=0||xx>n||yy<=0||yy>m)continue;
            char want;
            if(g[t.x][t.y]=='A')
            {
                if(t.cnt==k)want='B';
                else want='A';
            }
            else
            {
                if(t.cnt==k)want='A';
                else want='B';
            }
            if(g[xx][yy]!=want)continue;
            int ncnt,cnt=t.cnt;
            if(want==g[t.x][t.y])ncnt=cnt+1;
            else ncnt=1;
            if(dist[xx][yy][ncnt]>dist[t.x][t.y][cnt]+1)
            {
                dist[xx][yy][ncnt]=dist[t.x][t.y][cnt]+1;
                q.push({xx,yy,ncnt});
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(dist,0x3f,sizeof dist);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)cin>>g[i][j];
    bfs();
    int ans=0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=k;i++)
        ans=min(ans,dist[n][m][i]);
    if(ans<=0x3f3f3f3f3f3f3f3f/2)cout<<ans<<endl;
    else cout<<-1<<endl;
    return 0;
}