#include <bits/stdc++.h>
using namespace std;
struct coord
{
int x, y;
};
coord dfs(int dir, int x, int y, vector<vector<vector<coord>>> &Goto, vector<coord> &Tr, vector<string> &Grid)
{
int dir2 = dir;
if (Grid[x][y] == 'A')
dir2 = (dir + 3) % 4;
if (Grid[x][y] == 'C')
dir2 = (dir + 1) % 4;
if (Goto[dir][x][y].x != -1)
return Goto[dir][x][y];
Goto[dir][x][y] = {-2, -2};
int x2 = x + Tr[dir2].x, y2 = y + Tr[dir2].y;
if (x2 < 0 || y2 < 0 || x2 >= Grid.size() || y2 >= Grid[0].size())
Goto[dir][x][y] = {x, y};
else if (Grid[x2][y2] == 'x')
Goto[dir][x][y] = {x, y};
else
Goto[dir][x][y] = dfs(dir2, x2, y2, Goto, Tr, Grid);
return Goto[dir][x][y];
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int N, W, H;
cin >> N >> W >> H;
vector<string> Grid(H);
for (int i = 0; i < H; i++)
cin >> Grid[i];
vector<coord> Tr = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
vector<vector<vector<coord>>> Goto(4, vector<vector<coord>>(H, vector<coord>(W, {-1, -1})));
for (int i = 0; i < H; i++)
{
for (int j = 0; j < W; j++)
{
for (int dir = 0; dir < 4; dir++)
{
if (Goto[dir][i][j].x != -1)
continue;
dfs(dir, i, j, Goto, Tr, Grid);
}
}
}
vector<vector<vector<vector<int>>>> dp(N, vector<vector<vector<int>>>(N, vector<vector<int>>(H, vector<int>(W, 100000000))));
for (int i = 0; i < H; i++)
{
for (int j = 0; j < W; j++)
{
int temp = Grid[i][j] - '1';
if (temp >= 0 && temp <= 8)
dp[temp][temp][i][j] = 0;
}
}
int best = 100000000;
for (int sz = 1; sz < N; sz++)
{
for (int l = 0; l < N - sz + 1; l++)
{
int r = l + sz - 1;
priority_queue<vector<int>> PQ;
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++)
PQ.push({-dp[l][r][i][j], i, j});
while (!PQ.empty())
{
int x = PQ.top()[1], y = PQ.top()[2], t = -PQ.top()[0];
PQ.pop();
if (dp[l][r][x][y] != t)
continue;
for (int k = 0; k < 4; k++)
{
if (Goto[k][x][y].x == -2)
continue;
if (dp[l][r][Goto[k][x][y].x][Goto[k][x][y].y] <= t + 1)
continue;
dp[l][r][Goto[k][x][y].x][Goto[k][x][y].y] = t + 1;
PQ.push({-t - 1, Goto[k][x][y].x, Goto[k][x][y].y});
}
}
}
for (int l = 0; l < N - sz; l++)
{
int r = l + sz;
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++)
for (int k = l; k < r; k++)
dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][k][i][j] + dp[k + 1][r][i][j]);
}
}
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++)
best = min(best, dp[0][N - 1][i][j]);
cout << best;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |