CF877D Olya and Energy Drinks 题解

· · 题解

这道题是蓝题好像多余了。

一看到最短时间，我们第一反应就是 BFS，但是这道题仅仅 BFS 不够，要加一些剪枝优化，例如对下面这个例子：

4 4 10
..#.
...#
..##
.###
1 1 3 2

第一，我们从坐标 (1,1) 出发，这时我们可以向右 1~10 步，但是我们发现当我们走 2 步时已经有一个 # 了，这时我们可以直接跳出循环，因为后面已经不可能了。

第二，从坐标 (1,1) 出发，我们可以向下 10 格，但是走了 4 格就已经越界了，那我们也不用走了，为什么呢？因为，若 a+b>n，且有一数 c 满足 c>b，则 a+c>n（废话）。

稍微注意一下这几点就好了，至于状态压缩我是没用，也过了：

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;

int n, m, p;
const int N = 1e3 + 5;
char ch[N][N];
int start_x, start_y, end_x, end_y;
bool visit[N][N];

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

struct Node
{
    int x, y, times;
};

void bfs()
{
    queue<Node> q;
    Node l;
    l.x = start_x;
    l.y = start_y;
    l.times = 0;
    q.push(l);
    visit[start_x][start_y] = true;
    while (!q.empty())
    {
        Node k = q.front(), s;
        q.pop();
        s.times = k.times + 1;
        for (int i = 0; i < 4; i++)
        {
            for (int j = 1; j <= p; j++)
            {
                s.x = k.x + dx[i] * j;
                s.y = k.y + dy[i] * j;
                if (s.x <= 0 || s.x > n || s.y <= 0 || s.y > m || ch[s.x][s.y] == '#') break;
                if (visit[s.x][s.y]) continue;
                visit[s.x][s.y] = true;
                q.push(s);
                if (s.x == end_x && s.y == end_y)
                {
                    cout << s.times << endl;
                    return;
                }
            }
        }
    }
    cout << "-1\n";
}

int main()
{
    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++) cin >> ch[i][j];
    }
    cin >> start_x >> start_y >> end_x >> end_y;
    if (start_x == end_x && start_y == end_y)
    {
        cout << "0\n";
        return 0;
    }
    bfs();
    return 0;
}