F - Pond Skater 矩阵 一个方向走k步。。最短路
这种矩阵走k步的问题。。一般都是选择直接🔥暴力k次。。然后严格控制入队的条件。
// 按照四个方向状态去写。也是能写。。但是会特别恶心。。因为你要算 剩下的可用步数。。这个步数+1 -1 之间。。很容易乱。。而且初始化统一步数也麻烦
// 虽然我也写出来了。哈哈哈。。
//
// 直接用最短路。暴力k。。。这种题型。。好像就是这样的。。。他的复杂度不知道怎么证明。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128_t
#define ar array<int, 2>
#define arr array<int, 3>
int n, m, k, inf = 1LL << 61, mod = 998244353;// 1e9+7;
const int N = 5e5 + 50;
void solve() {
cin >> n >> m >> k;
int a, b, c, d;
cin >> a >> b >> c >> d;
a--, b--, c--, d--;
int e[5] = {1, 0, -1, 0, 1};
string g[n];
for (auto&x : g)
cin >> x;
vector f(n, vector<int>(m, inf));
priority_queue<arr, vector<arr>, greater<arr>>q;
q.push({0, a, b});
f[a][b] = 0;
while (q.size()) {
auto[t, x, y] = q.top(); q.pop();
// cout << t << " " << x << " " << y << '\n';
if (f[x][y] != t)continue;
for (int i = 0; i < 4; ++i) {
for (int j = 1; j <= k; ++j) {
int l = x + e[i] * j, r = y + e[i + 1] * j;
if (l < 0 || r < 0 || l >= n || r >= m )
continue;
if ( f[l][r] <= f[x][y] || g[l][r] != '.')
break;//这边要断掉。。而不是continue
if (f[l][r] > t + 1) {//这边== 也不行放入。。这个细节很重要 不然直接TLE
f[l][r] = t + 1;
q.push({f[l][r], l, r});
}
}
}
}
cout << (f[c][d] == inf ? -1 : f[c][d]);
};
// 这题主要在实现。。。。很容易些的非常麻烦。
// 直接爆搜的。。。很牛逼的。大大简化实现难度
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(15);
#ifdef DEBUG
freopen("../1.in", "r", stdin);
#endif
//init_f();
//init();
//expr();
// int T; cin >> T; while(T--)
solve();
return 0;
}
感受下 当时写4方向状态的。。恶心程度！！
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128_t
#define ar array<int, 2>
#define arr array<int, 5>
int n, m, k, inf = 1LL << 61, mod = 998244353;
const int N = 2e3 + 50;
void solve() {
cin >> n >> m >> k;
int sx, sy, tx, ty;
cin >> sx >> sy >> tx >> ty;
vector a(n + 2, vector<char>(m + 2, '#'));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> a[i][j];
std::vector<std::vector<std::vector<std::array<int, 2>>>> d(n + 2, std::vector<std::vector<std::array<int, 2>>>(m + 2, std::vector<std::array<int, 2>>(4, {inf, -inf})));
// 本质上是一个 ar d[n][m][4] 。。。的一个数组。不过他这里n m大小不确定范围所以只能开成vector 还用gpt 帮忙开的。。都忘记
// 就是四个方向还剩下几步免费的可以走。。
//首先权重是 最短。。然后 剩下的最多。。
priority_queue<arr, vector<arr>, greater<arr>>q;
for (int i = 0; i < 4; ++i) {
d[sx][sy][i][0] = 1;
d[sx][sy][i][1] = -k; //还剩多少 初始点比较特殊 还能走完整的k步。。其他的时候 只要迈出去了 都是剩下 -k+1
q.push({1, -k, sx, sy, i});
}
int dx[5] = {1, 0, -1, 0, 1};
while (q.size()) {
auto[s, t, x, y, id] = q.top(); q.pop();
if (d[x][y][id] > ar{s, t})
continue;
for (int i = 0; i < 4; ++i) {
int l = x + dx[i], r = y + dx[i + 1];
int s2, c;
if (i == id) {//这边分类就是如果方向相同。。就继续走。。
s2 = s, c = t;
if (++c == 1) {
s2++; c = -k + 1 ;
}
} else {//方向不同。直接+1 。。这边是重置为 -k+1 还能走的步数。
s2 = s + 1, c = -k + 1;
}
if (a[l][r] == '.' && d[l][r][i] > ar{s2, c}) {
d[l][r][i] = {s2, c};
q.push({s2, c, l, r, i});
}
}
}
int ans = inf;
for (int i = 0; i < 4; ++i)
ans = min(ans, d[tx][ty][i][0]);
cout << (ans == inf ? -1 : ans);
};
// 其实这题很简单 d[i][j][方向] 这种题型的一个扩展而已。。
// 又加了一个权重 就是 d[i][j][方向][当前方向能走的剩余步数]。。。。。
// 就这么简单。然后要想好 你剩余多少步。。这个细节 是-k 还是-k+1 。。
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(15);
#ifdef DEBUG
freopen("../1.in", "r", stdin);
#endif
//init_f();
//init();
//expr();
// int T; cin >> T; while(T--)
solve();
return 0;
}