P9860 题解

zhuweiqi · 2023-11-14 20:10:05 · 题解

题目大意：给你一个迷宫，其中每个格子可能会有移动方式的限制，求从左上角走到右下角的最少步数。

思路：首先，我们需要排除起点或终点为 * 的情况，此时显然无解，输出 -1。否则，对全图进行一遍 bfs，记 f_{i,j} 为从 (1,1) 走到 (i,j) 的最少步数，初始时需要将 f 数组全部赋值为 -1，其中对于当前格子（设为 (x,y)）的扩展，需要分类讨论，如果 a_{x,y} 为 *，则不能进行扩展；如果 a_{x,y} 为 |，则只能上下扩展，即只能走到横坐标为 x\pm1 且纵坐标为 y 的格子（前提是这些格子在边界范围之内且尚未被扩展过，下同）；如果 a_{x,y} 为 -，则只能左右扩展，即只能走到横坐标为 x 且纵坐标为 y\pm1 的格子；如果 a_{x,y} 为 +，则上下左右都可以扩展，即可以走到横坐标为 x\pm1 且纵坐标为 y\pm1 的格子。最终，答案即为 f_{n,m} 的值，特别地，由于题目中说道：初始时在左上角和在右上角结束时都算 1 步，故我们需要将 f_{1,1} 的初始值赋值为 1。

参考代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[22][22];
int f[22][22];
queue<pair<int,int>> q;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
bool bj(int x,int y){return x>=1 && x<=n && y>=1 && y<=m;}
void bfs(){
    memset(f,-1,sizeof(f));
    f[1][1]=1;
    q.push({1,1});
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        int i,j;
        if(a[x][y]=='|') i=0,j=2;
        if(a[x][y]=='-') i=2,j=4;
        if(a[x][y]=='+') i=0,j=4;
        if(a[x][y]=='*') continue;
        for(;i<j;i++){
            int nx=x+dir[i][0];
            int ny=y+dir[i][1];
            if(bj(nx,ny) && f[nx][ny]==-1){
                f[nx][ny]=f[x][y]+1;
                q.push({nx,ny});
            }
        }
    }
    return;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
        if(a[1][1]=='*' || a[n][m]=='*'){
            printf("-1\n");
            continue;
        }
        bfs();
        printf("%d\n",f[n][m]);
    }
    return 0;
}