飞羽疾电 (kujou)

题目描述

天狗以迅捷见长，九条裟罗熟稔稻妻地理，经常快速往来各地执行公务。九条裟罗在稻妻执行探索派遣任 务时，需要事先规划路线。

具体地，稻妻的地图可以描述为一个大小为 n 行 m 列的网格地图。每个格子上可能有障碍物，有障碍物 的格子无法通行。为了方便，九条裟罗用 0 表示该格子上无障碍物，1 表示该格子上有障碍物。保证起点和终点上没有障碍物。

现在九条裟罗要从起点 (sx,sy) 走到终点 (tx,ty) 完成探索派遣任务。九条裟罗每次可以选择向上下左右 方向走一格。她有一个特殊技能，使得她每次上下移动一步用时 k 秒，左右移动一步用时 1 秒。

作为天狗将军的九条裟罗还需要往返各地完成雷电将军的公务，所以作为旅行者的你需要帮助九条裟罗选定一个 k，使得从起点到终点的最短用时等于 s。

注意：k 不能为负，保证有唯一解

输入格式

第一行：两个正整数 n,m。

第二行：四个正整数 sx,sy,tx,ty ，分别表示起点所在行数、列数，终点所在行数、列数。

接下来 n 行，每行 m 个数，描述稻妻的地图。 最后一行：一个正实数 s。

输出格式

输出仅一行：一个实数 k，表示答案，四舍五入保留 3 位小数。

样例 #1

样例输入 #1

4 4 
1 1 4 4 
0 0 1 1 
1 0 0 0 
0 0 1 0 
0 0 0 0 
5.00

样例输出 #1

0.667

提示

对于所有数据，满足 1 \le n,m \le 100，1 \le s \le 10^5，1 \le sx,tx \le n，1 \le sy,ty \le m。

• 特殊性质 A：n, m \leq 10，且保证从起点到终点只有一条不重复经过同一个点的路径。

我的代码

#include <algorithm>
#include <array>
#include <bitset>
#include <cstdint>
#include <cstdlib>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <ranges>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <queue>

using int64 = std::int64_t;

template<class ...Args>
void input(Args&&...args){
    (std::cin>>...>>std::forward<Args>(args));
}

template<class T>
std::remove_cv_t<T> input(){
    std::remove_cv_t<T> t;
    std::cin>>t;
    return t;
}

template<class ...Args>
void print(Args&&...args){
    (std::cout<<...<<args);
}

struct Point{
    int64 x, y;
    // bool operator<(const Point &that)const{
    //     return (this->x + this->y) < (that.x + that.y);
    // }
    bool operator==(const Point &that)const{
        return this->x == that.x && this->y == that.y;
    }
};

using Vector2 = Point;
using Status = std::pair<Vector2, Point>;

const int64 max_n = 100 + 5;
int64 _map[max_n][max_n];
const int64 (&map)[max_n][max_n] = _map;
std::bitset<max_n> vis[max_n];
const std::array<std::array<int64, 2>, 4> dir{{
    {0, 1},
    {1, 0},
    {-1, 0},
    {0, -1}
}};

int main(){
    std::iostream::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
    std::cout<<std::fixed<<std::setprecision(3);

    const int64 n = input<decltype(n)>(), m = input<decltype(m)>();

    const auto inputPoint = []()->Point{
        Point ret;
        input(ret.x, ret.y);
        return ret;
    };
    const Point start = inputPoint(), end = inputPoint();

    std::ranges::for_each(std::ranges::views::iota(1, n+1), [&](const auto &i){
        std::ranges::for_each(std::ranges::views::iota(1,m+1), [&](const auto &j){
            input(_map[i][j]);
        });
    });

    const double ansScore = input<double>();

    std::queue<Status> q;
    q.emplace(Vector2{0, 0}, start);
    vis[start.x][start.y] = true;

    const Vector2 ansVec = [&]()->Vector2{
        while(!q.empty()){
            const auto top = q.front();
            q.pop();

            if(top.second == end){
                return top.first;
            }

            for (const auto i : dir) {
                const Point nextPoint = {top.second.x + i[0], top.second.y + i[1]};
                if(map[nextPoint.x][nextPoint.y] == 1 || nextPoint.x < 1 || nextPoint.x > n 
                    || nextPoint.y < 1 || nextPoint.y > m
                    || vis[nextPoint.x][nextPoint.y]
                ){
                    continue;
                }
                vis[nextPoint.x][nextPoint.y] = true;
                q.emplace(Vector2{.x = top.first.x + std::abs(i[0]), .y = top.first.y + std::abs(i[1])}, nextPoint);
            }
        }
        throw std::runtime_error("unreachable");
    }();

    const double udTimes = ansScore - (double)ansVec.y;
    print(udTimes/ansVec.x);
}