#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define ll long long
const int N = 505;
char a[N][N];
int mp[N][N], n, w, h, ind[10], nd, dpfn[10][10][N*N];
pair <int, int> dp[N][N][4];
vector <vector <int>> v;
pair <int, int> f(int i, int j, int x) {
if(dp[i][j][x] != pair <int, int> {0, 0}) return dp[i][j][x];
int x1 = (x % 2 ? 0 : (!x ? -1 : 1)), y1 = (!(x % 2) ? 0 : (x == 1 ? 1 : -1));
if(a[i + x1][j + y1] != 'x' and i + x1 <= h and i + x1 > 0 and j + y1 <= w and j + y1 > 0) {
int xx = x, i1 = i, j1 = j;
i += x1, j += y1;
if(a[i][j] == 'C') {
x++;
if(x == 4) x = 0;
}
if(a[i][j] == 'A') {
x--;
if(x == -1) x = 3;
}
return dp[i1][j1][xx] = f(i, j, x);
}
return dp[i][j][x] = pair <int, int> {i, j};
}
void compute(int a, int b, vector <pair <int, int>>&q2){
queue<pair<int,int> > q;
while(!q.empty() or !q2.empty()) {
bool ok = 0;
if (q2.empty())
ok = 1;
else if (!q.empty() && q.front().first < q2.back().first)
ok = 1;
auto [cost, x] = ok ? q.front() : q2.back();
if (ok)
q.pop();
else
q2.pop_back();
for(auto i : v[x]) {
if(dpfn[a][b][i] > cost+1) {
dpfn[a][b][i] = cost+1;
q.push({dpfn[a][b][i], i});
}
}
}
}
void fn(int a, int b) {
vector <pair <int, int>> q;
for(int k = a; k < b; k++)
for(int node = 1; node <= nd; node++)
dpfn[a][b][node] = min(dpfn[a][b][node], dpfn[a][k][node] + dpfn[k+1][b][node]);
for(int k = a; k < b; k++)
for(int node = 1; node <= nd; node++)
if(dpfn[a][b][node] != 1e9)
q.push_back({dpfn[a][b][node], node});
sort(q.begin(), q.end(), greater<pair<int,int>>());
compute(a, b, q);
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> w >> h;
for(int i = 1; i <= h; i++) {
for(int j = 1; j <= w; j++) {
cin >> a[i][j];
mp[i][j] = ++nd;
if(a[i][j] >= '1' and a[i][j] <= '9') ind[a[i][j] - '0'] = nd;
}
}
for(int i = 1; i <= n; i++) {
for(int i1 = 1; i1 <= n; i1++) {
for(int i2 = 1; i2 <= nd; i2++) {
dpfn[i][i1][i2] = 1e9;
}
}
}
v.resize(nd+1);
for(int i = 1; i <= h; i++) {
for(int j = 1; j <= w; j++) {
for(int k = 0; k < 4; k++) {
pair <int, int> ind = f(i, j, k);
if(ind != pair <int, int> {i, j}) v[mp[i][j]].push_back(mp[ind.ff][ind.ss]);
}
}
}
vector <pair <int, int>> q;
for(int i = 1; i <= n; i++) {
dpfn[i][i][ind[i]] = 0;
q.push_back({0, ind[i]});
compute(i, i, q);
}
for(int i = 0; i < n; i++)
for(int a = 1; a + i <= n; a++)
fn(a, a + i);
int ans = 1e9;
for(int i = 1; i <= nd; i++)
ans = min(ans, dpfn[1][n][i]);
cout << (ans == 1e9 ? -1 : ans) << "\n";
return 0;
}
# | 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... |