算法1
(纯bfs + 预处理障碍) $O(n^2 * k(最坏))$
blablabla
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
char g[3][310][310];
bool st[310][310];
int n, m, k;
struct Node
{
int t, x, y;
};
int bfs()
{
PII S = {3, 3};
PII E = {n - 2, n - 2};
int dx[5] = {1, -1, 0, 0, 0};
int dy[5] = {0, 0, 1, -1, 0};
queue<Node> q;
q.push({0, S.x, S.y});
st[S.x][S.y] = true;
while (q.size())
{
auto t = q.front(); q.pop();
int flag = min(t.t / k, 2);
if (flag != 2) q.push({t.t + 1, t.x, t.y});
for (int i = 0; i < 4; i ++ )
{
int ax = dx[i] + t.x, ay = dy[i] + t.y, at = t.t + 1;
if (ax < 1 || ax > n || ay < 1 || ay > m || g[flag][ax][ay] == '*') continue;
if (!st[ax][ay])
{
st[ax][ay] = true;
PII tt = {ax, ay};
if (E == tt) return at;
q.push({at, ax, ay});
}
}
}
return -1;
}
int main()
{
scanf("%d%d", &n, &k);
m = n;
for (int i = 1; i <= n; i ++ )
// cin >> g[2][i] + 1;
scanf("%s", g[2][i] + 1);
int dx[9] = {-1, 0, 1, 1, 1, 0, -1, -1, 0};
int dy[9] = {1, 1, 1, 0, -1, -1, -1, 0, 0};
for (int i = 2; i > 0; i -- )
for (int j = 1; j <= n; j ++ )
for (int k = 1; k <= n; k ++ )
{
if (g[i][j][k] == '*')
{
for (int u = 0; u < 9; u ++ )
{
int ax = j + dx[u], ay = k + dy[u];
if (ax < 1 || ax > n || ay < 1 || ay > m) continue;
g[i - 1][ax][ay] = '*';
}
}
}
printf("%d", bfs());
}