题解：P1735 字母迷宫

_Liyx_ · 2024-07-09 17:09:58 · 题解

思路

第一眼是一道 BFS，直到看到了天堂之门。所以用 DFS 写了一下，直接 TLE40。记录

相信各位停留在 A 处和 B 处的代码都会写，所以来讲一下停留在 C 处的代码。

在 C 处要停一步再走，所以可以定义一个 flag，当到了 C 处时，判断 flag 是否为 1，如果为 0，将 flag 修改为 1，并将步数也加 1，然后重新加入到队列里，这样可以做到停一步的效果；如果为 1，说明已经停留过了，所以正常的进行 BFS 就好了。

最后放上 AC 代码。

代码

#include <bits/stdc++.h>
using namespace std;
int n;
char a[1205][1205];
bool vis[1205][1205];
int d1[2][5]={{1,0,-1,0},{0,1,0,-1}};
int d3[2][5]={{1,1,-1,-1},{-1,1,1,-1}};
struct node{
    int x,y,step;
    bool flag;
};
bool flag;
void bfs(){
    queue<node> q;
    if(a[1][1]!='*') q.push(node{1,1,1,0});
    if(a[1][n]!='*') q.push(node{1,n,1,0});
    if(a[n][1]!='*') q.push(node{n,1,1,0});
    while(!q.empty()){
        node now=q.front();
        q.pop();
        if(now.x==n&&now.y==n){
            //标记 
            flag=1;
            cout<<now.step;
            return;
        }
        if(a[now.x][now.y]=='A'){
            for(int i=0;i<4;i++){
                int xx=now.x+d1[0][i],yy=now.y+d1[1][i];
                if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&!vis[xx][yy]&&a[xx][yy]!='*'){
                    vis[xx][yy]=1;
                    q.push(node{xx,yy,now.step+1,0});
                }
            }
        }
        else if(a[now.x][now.y]=='B'){
            for(int i=0;i<4;i++){
                //在B处会传送2格，乘以2 
                int xx=now.x+2*d1[0][i],yy=now.y+2*d1[1][i];
                if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&!vis[xx][yy]&&a[xx][yy]!='*'){
                    vis[xx][yy]=1;
                    q.push(node{xx,yy,now.step+1,0});
                }
            }
        }
        else if(a[now.x][now.y]=='C'){
            //对于聚气的处理 
            if(now.flag==0){
                q.push(node{now.x,now.y,now.step+1,1});
                continue;
            }

            //flag不为0则正常进行BFS 
            for(int i=0;i<4;i++){
                int xx=now.x+d3[0][i],yy=now.y+d3[1][i];
                if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&!vis[xx][yy]&&a[xx][yy]!='*'){
                    vis[xx][yy]=1;
                    q.push(node{xx,yy,now.step+1,0});
                }
            }
        }
    }

}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) cin>>a[i][j];
    //如果a[n][n]本身为障碍则无解 
    if(a[n][n]=='*'){
        cout<<"No answer";
        return 0;
    }
    bfs();
    //如果没有输出则无解 
    if(flag==0){
        cout<<"No answer";
        return 0;
    }
    return 0;
}