CF877D Olya and Energy Drinks

· · 题解

返回题目

一道纯 BFS 题，只是相比其他普通 BFS 题多了“可以移动 1 \sim k 步”一点。

这道题的思路就是：从给定的起点开始，BFS 搜索每一个点所能到达的点，并把每一个到过的点做标记，还要记录走到这一个点需要的最少步数。当第一次搜到终点时就停住搜索，输出走到终点需要的最少步数。

这其中有几点要注意：

  1. 如果起点、终点有其一是障碍物，就直接输出 -1。
  2. 如果起点和终点相同，就直接输出 0。
  3. 当搜索一个点时发现了障碍，就直接跳出这个方向的点枚举。

具体 AC 代码见下： 

#include<bits/stdc++.h>
using namespace std;

int n,m,k;
int sx,sy,fx,fy;
char c[1010][1010];
int step[1010][1010];//记录的数组
bool f[1010][1010];//标记步数的数组
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};//用于枚举四个方向x轴和y轴的变化值 
queue<pair<int,int> >q;//STL的queue和pair，存点的坐标 
void bfs()
{
    q.push(make_pair(sx,sy));
    f[sx][sy]=1;
    step[sx][sy]=0;//将起点赋为0，后面需要累加的
    while(!q.empty())//只要队列非空就继续搜
    {
        int x=q.front().first;
        int y=q.front().second;//提取队首的两个坐标 
        q.pop();
        for(int i=0;i<4;i++)//枚举东南西北 
            for(int j=1;j<=k;j++)
            {
                int xx=x+dx[i]*j;//向 东/西/南/北 走j步 
                int yy=y+dy[i]*j;
                if(xx>=1&&xx<=n&&yy>=1&&yy<=m)
                {
                    if(c[xx][yy]=='#')
                        break;//如果遇到障碍的话后面的点就不用遍历了 
                    if(f[xx][yy]==0)
                    {
                        f[xx][yy]=1;//标记该点已来过 
                        q.push(make_pair(xx,yy));//放进队列一会搜
                        step[xx][yy]=step[x][y]+1;//需要的步数在上一步的基础上加一 
                        if(xx==fx&&yy==fy)
                            return;//找到终点就停搜
                    }
                }
            }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>c[i][j],
            step[i][j]=-1;//step初始化，并且不需要用memset 
    cin>>sx>>sy>>fx>>fy;
    if(c[sx][sy]=='#'||c[fx][fy]=='#')//特判起点或终点都是障碍 
    {
        cout<<"-1";
        return 0; 
    }
    if(sx==fx&&sy==fy)//特判起点等于终点的情况 
    {
        cout<<"0";
        return 0;
    }
    bfs();//进行搜索 
    cout<<step[fx][fy];//由于先前已经初始化，因此没搜到会输出-1 
    return 0;
}