dfs超时版

本人一般做这种题喜欢用dfs而不是bfs，所以上来先用dfs搞一下，dfs一条路走到黑,不出意外超时了
这题有个特点就是之前的路可以重复走，这就导致这个用dfs时间复杂度爆炸（几个点之间来回反复横跳）

void dfs(int l,int r,int t,char a)

这四个参数：（l,r）目前坐标，t是下一个所处的步数，a是下一个应该是A还是B

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
char shu[N][N];
//bool use[N][N];
int n,m,k;
int ans=0x3f3f3f3f;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
void dfs(int l,int r,int t,char a)
{
    if(l==n&&r==m)
    {
        ans=min(ans,t-1);
        return;
    }
    if(t-1>ans||t-1>100)//t-1>100属于瞎jb剪，防止几个点之间来回反复横跳
    {
      return;
    }
    for(int i=0;i<4;i++)
    {
        int x=l+dx[i],y=dy[i]+r;
        if(x>=1&&x<=n&&y>=1&&y<=m&&shu[x][y]==a)
        {
            if((t+1)/k%2==0)
            {
                dfs(x,y,t+1,'A');
            }
            else
            {
                dfs(x,y,t+1,'B');
            }
        }
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>shu[i][j];
        }
    }
    if(1/k%2==0)
    {
        dfs(1,1,1,'A');
    }
    else
    {
        dfs(1,1,1,'B');
    }
    if(ans==0x3f3f3f3f)
    {
        cout<<"-1";
    }
    else
    {
        cout<<ans;
    }
    return 0;
}

通过情况

bfs正解版

还没写