题目解析

阅读完题目可知题目要求的是：从起点(1,1)到终点(r,c)的最短路。且在迷宫中，可视为边权为1，也就是一个单源的无权最短路问题。那么我们可以采用BFS来解决这个问题。

BFS求最短路框架

void bfs(int sx,int sy){//从(sx,sy)出发
    queue<node> q;
    q.push(node{sx,sy});//起点入队
    vis[sx][sy]=1;//标记起点
    ans[sx][sy]=1;//记录起点的最短步数
    while(!q.empty()){//循环直到队列为空
        node cur=q.front();
        q.pop();
        for(int i=L;i<R;i++){//遍历邻接点
            int nx=cur.x+dx[i],ny=cur.y+dy[i];//计算下一步位置
            if(!check(nx,ny)) continue;//不能到达的位置跳过
            vis[nx][ny]=1;
            ans[nx][ny]=ans[cur.x][cur.y]+1;//更新最短路
            q.push(node{nx,ny});
        }
    }
}

需要注意本题的行走方式，在*不能行走，+上下左右都可以，-只能左右，|只能上下。那么我们需要根据不同情况处理不同的行走方式。并且注意起点部分为的最短路为1.

完整代码

#include <bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
};
int r,c;
char a[25][25];
int ans[25][25];
bool vis[25][25];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
void bfs(int sx,int sy){//从(sx,sy)出发
    queue<node> q;
    q.push(node{sx,sy});
    vis[sx][sy]=1;//起点入队
    ans[sx][sy]=1;//记录起点的最短步数
    while(!q.empty()){//循环直到队列为空
        node cur=q.front();
        q.pop();
        int L=0,R=0;
        if(a[cur.x][cur.y]=='+'){
            L=0;R=4;
        }else if(a[cur.x][cur.y]=='-'){
            L=2;R=4;
        }else if(a[cur.x][cur.y]=='|'){
            L=0;R=2;
        }
        for(int i=L;i<R;i++){//遍历邻接点
            int nx=cur.x+dx[i],ny=cur.y+dy[i];//计算下一步位置
            //不能到达的位置跳过
            if(nx<1||nx>r||ny<1||ny>c) continue;
            if(vis[nx][ny]||a[nx][ny]=='*') continue;
            vis[nx][ny]=1;
            ans[nx][ny]=ans[cur.x][cur.y]+1;//更新最短路
            q.push(node{nx,ny});
        }
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        //注意多组数据清空
        memset(ans,-1,sizeof(ans));
        memset(vis,0,sizeof(vis));
        memset(a,0,sizeof(a));
        cin>>r>>c;
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                cin>>a[i][j];
            }
        }
        bfs(1,1);
        cout<<ans[r][c]<<endl;
    }
    return 0;
}