G.AB路线【蓝桥杯】/bfs+可重复走

AB路线

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

bfs+可重复走

思路:本题和传统的bfs题目不同,本题为了满足题目先走K个A再走K个B,可能需要重复走某个格子才能继续走下去,故vis数组可以多开一维,vis[x][y][z]表示第z次走到x行y列这种情况是否出现过
A A A B B B A A A
0 1 2 3 4 5 6 7 8
比如到7这个时,6%(2*k)=0,表示是k次中第0次到达,如果前面已经出现过k次中第0次到达该点这种情况则代表重复了,不行

#include<iostream>
#include<queue>
using namespace std;
struct node
{
    int x,y,path;
};
char a[1005][1005];
int xx[4]={0,1,0,-1};
int yy[4]={1,0,-1,0};
int vis[1005][1005][12];
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>a[i][j];
    if(a[0][0]!='A')
    {
        cout<<-1<<endl;
        return 0;
    }
    queue<node> q;
    q.push({0,0,0});
    vis[0][0][0]=1;
    bool flag=0;
    int res;
    while(!q.empty())
    {
        int x=q.front().x;
        int y=q.front().y;
        int p=q.front().path;
        q.pop();
        //p表示现在是要走第几步
        p++;
        char c;
        //当可以整除k时表示要改变字符
        if(p%k==0) 
        {
            (a[x][y]=='A')?c='B':c='A';
        }
        else 
        {
            c=a[x][y];
        }
        for(int i=0;i<4;i++)
        {
            int nx=x+xx[i];
            int ny=y+yy[i];
            if(nx<0||nx>=n||ny<0||ny>=m) continue;
            //p%(2*k)表示现在是k次中第几次走到该点(从0开始)
            if(vis[nx][ny][p%(2*k)]) continue;
            if(a[nx][ny]!=c) continue;
            q.push({nx,ny,p});
            vis[nx][ny][p%(2*k)]=1;
            if(nx==n-1&&ny==m-1) 
            {
                flag=1;
                res=p;
                break;
            }
        }
        if(flag) break;
    }
    if(flag) cout<<res<<endl;
    else cout<<-1<<endl;
    return 0;
}

相关推荐

  1. BFS

    2024-05-11 22:16:06       36 阅读
  2. 方格》

    2024-05-11 22:16:06       57 阅读
  3. 每日一题(BFS

    2024-05-11 22:16:06       41 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-05-11 22:16:06       98 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-05-11 22:16:06       106 阅读
  3. 在Django里面运行非项目文件

    2024-05-11 22:16:06       87 阅读
  4. Python语言-面向对象

    2024-05-11 22:16:06       96 阅读

热门阅读

  1. STM32-DAC

    STM32-DAC

    2024-05-11 22:16:06      31 阅读
  2. c++中unrodered_map与unordered_set的基本使用

    2024-05-11 22:16:06       33 阅读
  3. 基于Seata实现分布式事务实现

    2024-05-11 22:16:06       36 阅读
  4. ffmpeg 7.0 + vs2022 +windows编译

    2024-05-11 22:16:06       36 阅读
  5. Idea 核心编程快捷键-简洁版

    2024-05-11 22:16:06       30 阅读
  6. 嵌入式复习提纲

    2024-05-11 22:16:06       31 阅读
  7. 学习笔记:IEEE 1003.13-2003【POSIX PSE53接口列表】

    2024-05-11 22:16:06       29 阅读