0完ですがHack１成功でレートは若干プラス。
Div1 Easy FlightPlan
使える高さを固定すれば、スタートからゴールまで最低何歩で行けるかはBFSで書けるので、高さを全探索すれば良い。ただ、$O(N^4)$をPythonで通すのは無理。頑張ってC++を書いたものの、システムテストで落ちてしまった。
注意すべきは二点。
・（BFSの書き方にもよるけど）スタート地点が全探索時の高さより高いときバグる可能性がある。
・オーバーフロー。全探索する高さをintにしていたら、高さ*cupなどの計算でオーバーフローしていた。
この二つに引っ掛かってたのでダメ。特に一点目は、Pythonで書いててもミスってた可能性がありますね……。
#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
class FlightPlan
{
public:
long long fly(int R, int C, vector<int> H, int cup, int cdn, int clr)
{
set<long long> S;
S.clear();
vector<long long> DP(R * C);
for (int i = 0; i < R * C; i += 1)
{
DP[i] = 9999;
S.insert(H[i]);
}
DP[0] = 0;
long long ANS = 1000000000000000000;
for (auto s : S)
{
if (s < H[0])
{
continue;
}
if (s < H[R * C - 1])
{
continue;
}
deque<int> Q;
Q.push_back(0);
for (int i = 0; i < R * C; i += 1)
{
DP[i] = 9999;
}
DP[0] = 0;
while (Q.size())
{
int x = Q.front();
Q.pop_front();
int r = x / C;
int c = x % C;
if (r + 1 < R && H[(r + 1) * C + c] <= s && DP[(r + 1) * C + c] > DP[r * C + c] + 1)
{
DP[(r + 1) * C + c] = DP[r * C + c] + 1;
Q.push_back((r + 1) * C + c);
}
if (r - 1 >= 0 && H[(r - 1) * C + c] <= s && DP[(r - 1) * C + c] > DP[r * C + c] + 1)
{
DP[(r - 1) * C + c] = DP[r * C + c] + 1;
Q.push_back((r - 1) * C + c);
}
if (c + 1 < C && H[r * C + c + 1] <= s && DP[r * C + c + 1] > DP[r * C + c] + 1)
{
DP[r * C + c + 1] = DP[r * C + c] + 1;
Q.push_back(r * C + c + 1);
}
if (c - 1 >= 0 && H[r * C + c - 1] <= s && DP[r * C + c - 1] > DP[r * C + c] + 1)
{
DP[r * C + c - 1] = DP[r * C + c] + 1;
Q.push_back(r * C + c - 1);
}
if (DP[(R - 1) * C + C - 1] < 9999)
{
long long ANSX = 0;
ANSX += (s - H[0]) * cup;
ANSX += (s - H[(R - 1) * C + C - 1]) * cdn;
ANSX += DP[(R - 1) * C + C - 1] * clr;
if (ANS > ANSX)
{
ANS = ANSX;
}
}
}
}
return ANS;
}
};