题解：P1735 字母迷宫

· · 题解

前言

读完题，我们不难发现，这其实是一道广度优先搜索的题目。

//bfs模板
#include<bits/stdc++.h>
using namespace std;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};//方向数组 
int n,v[1001][1001],a1,a2,a3,a4;
char a[1001][1001];
int cheak(int x,int y)
{
    if(v[x][y]==0&&x>0&&y>0&&x<=n&&y<=n)return 1;
    //根据情境做改变 一般情况下还有a[x][y]=='某个字符' 
    return 0;
}
struct S{
    int x,y;
    int step;
}s1;
queue<S>q;
void bfs()
{
    while(!q.empty())q.pop();//如果有多组样例 每次队列要清空 
    v[a1][a2]=1;//起点已经走过了 
    q.push({a1,a2,0});
    while(!q.empty())
    {
         s1=q.front();
         if()//终止条件 
         {
           cout<<s1.step;//输出此刻的步数（不一定） 
           return;
         }
         q.pop();//队列的第一项既然给了s1 那么它就不要了 不然会死循环 
         for(int i=0;i<4;i++)//往上、下、左、右去看 
            if(cheak(s1.x+dx[i],s1.y+dy[i])==1)//可以走 
            {
              v[s1.x+dx[i]][s1.y+dy[i]]=1;//标记为已走过 
              q.push({s1.x+dx[i],s1.y+dy[i],s1.step+1});//注意步数要+1 
            }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];//输入数组 
    cin>>a1>>a2>>a3>>a4;//起点坐标和目的地坐标 
    bfs();
    return 0;
}

准备工作

1.定义方向数组（注意：C 和 AB 不一样，应该单独定一个方向数组往左上左下右上右下走）。

2.定义一个结构体，里面存放每时每刻的坐标、目前走的步数以及目前经过了多久。

3.定义一个队列（废话，bfs 当然要队列）。

题目分析

这道题我们可以分情况讨论。

如果 (x,y) 等于 A，那么分别判断上下左右是不是障碍，不是的话就标记为已走过，将此刻的坐标、步数和时间入队。

q.push({xx,yy,s1.step+1,s1.shi+1});

如果 (x,y) 等于 B，那么也分别判断上下左右是不是障碍，不是的话就标记为已走过，将此刻的坐标、步数和时间入队。

q.push({xx,yy,s1.step+2,s1.shi+1});

如果 (x,y) 等于 C,那么分别判断左上左下右上右下是不是障碍，不是的话就标记为已走过，将此刻的坐标、步数和时间入队。

q.push({xx,yy,s1.step+1,s1.shi+2});

好了，接下来就是普通的 bfs 了，相信聪明的你一定学会了吧！