题解 CF877D 【Olya and Energy Drinks】

耶耶小朋友 · 2020-12-19 15:46:45 · 题解

做法：

bfs即可，其实不难。

这可能是最易懂的代码，也是最慢的的代码了。

代码里有解释。

主题思路：

1.将起点丢到队列。

2.移动起点。

3.判断有没有往回走。

这步就比较关键了，避免走回去，能节省大概 1 s的时间。

4.有没有出界或踩到了路障。

5.走到终点返回答案，否则返回 -1。

Code:

#include<bits/stdc++.h>
using namespace std;
//考虑unsigned long long
typedef long long ll;
const int N = 1010;
//移动数组 
int fxy[5][2] = {{0,0},{0,1},{0,-1},{-1,0},{1,0}};
//路障数组 
int a[N][N];
//标记数组 
int vis[N][N];
//n,m,k,start_x,start_y,end_x,end_y 
int n,m,k;
int sx,sy,ex,ey;

struct OaED {
    //当前x,y，需要步数，从哪边来的 
    int x,y,step,fangxiang;
};

int bfs() {
    queue<OaED> q;
    //初始化起点 
    OaED az;
    az.x = sx,az.y = sy,az.step = 0;
    vis[sx][sy] = 1;
    q.push(az);
    //开搜 
    while (!q.empty()) {
        //取出队列第一项并弹掉 
        OaED b = q.front();
        q.pop();
        for (int i = 1;i <= 4;i++) {
            //判断是不是往回走，不判会慢一些 
            if ((b.fangxiang == 1 && i == 2) || 
            (b.fangxiang == 2 && i == 1) || 
            (b.fangxiang == 3 && i == 4) || 
            (b.fangxiang == 4 && i == 3)) {
                continue;
            }
            for (int j = 1;j <= k;j++) {
                //走后了的坐标 
                int x = b.x + fxy[i][0] * j;
                int y = b.y + fxy[i][1] * j;
                //去过就别来了 
                if (vis[x][y] == 1) {
                    continue;
                }
                //飞出地图或踩到路障就直接break 
                if (x <= 0 || x > n || y <= 0 || y > m || a[x][y] == 1) {
                    break;
                }
                OaED c;
                //更新 
                c.x = x,c.y = y,c.step = b.step + 1,c.fangxiang = i; 
                vis[x][y] = 1;
                //到了终点就返回步数值 
                if(x == ex && y == ey) {
                    return c.step;
                }
                //没到就丢进队列搜 
                q.push(c);
            }
        }
    }
    return -1;
}

int main () {
    //输入 
    scanf("%d%d%d",&n,&m,&k);
    char x;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> x;
            //初始化路障数组 
            if (x == '#') {
                a[i][j] = 1;
            }
        }
    } 
    scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
    //特判起点和终点相等 
    if (sx == ex && sy == ey)   puts("0");
    else printf("%d",bfs());
    return qwq;
}