///In the name of GOD
//#pragma GCC optimize("O2")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,fma")
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
const ll MXN = 500 + 2;
const ll MXK = 12;
const ll INF = 1e9;
const ll Tof = 8e4;
const ll TOF = 2e5;
ll n, m, k;
int dp[MXK][MXK][MXN][MXN];
pair<int, int> dest[MXN][MXN][4], Pr;
vector<pair<ll, ll>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // R, D, L, U
priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> pq;
string s[MXN];
bool vis[MXN][MXN][4], ok[MXN][MXN][4];
bool mark[MXN][MXN];
bool check(ll x, ll y){
return (1 <= x && x <= n && 1 <= y && y <= m);
}
void go(ll x, ll y, ll d){
if(vis[x][y][d]){
dest[x][y][d] = {-1, -1};
return;
}
if(ok[x][y][d]) return;
ll nd = d;
if(s[x][y] == 'A') nd = (nd + 3) % 4;
if(s[x][y] == 'C') nd = (nd + 1) % 4;
ll dx, dy; tie(dx, dy) = dir[nd];
if(check(x + dx, y + dy) && s[x + dx][y + dy] != 'x'){
vis[x][y][d] = 1;
go(x + dx, y + dy, nd);
dest[x][y][d] = dest[x + dx][y + dy][nd];
ok[x][y][d] = 1;
vis[x][y][d] = 0;
return;
}
dest[x][y][d] = {x, y};
ok[x][y][d] = 1;
}
void BFS(ll l, ll r){
pair<ll, ll> pr;
ll tof = Tof, tt = 0;
if(r - l + 1 >= n - 10) tof = 1e9, tt = -1e9;
while(!pq.empty() && tof){
int d; tie(d, pr) = pq.top(); pq.pop();
ll x, y; tie(x, y) = pr;
if(mark[x][y]) continue;
mark[x][y] = 1;
tof --;
for(int dr = 0; dr < 4; dr ++){
ll xp, yp; tie(xp, yp) = dest[x][y][dr];
if(xp == -1 || yp == -1 || mark[xp][yp]) continue;
if(d + 1 < dp[l][r][xp][yp]){
dp[l][r][xp][yp] = d + 1;
Pr = make_pair(xp, yp);
if(tt < TOF) pq.push({dp[l][r][xp][yp], Pr}), tt ++;
}
}
}
while(!pq.empty()) pq.pop();
}
int main(){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
memset(dest, -1, sizeof dest), memset(dp, 63, sizeof dp);
cin >> k >> n >> m; swap(n, m);
for(int i = 1; i <= n; i ++){
cin >> s[i];
s[i] = "$" + s[i];
}
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
if(s[i][j] == 'x') continue;
for(int d = 0; d < 4; d ++) go(i, j, d);
}
}
for(int i = 1; i <= k; i ++){
for(int x = 1; x <= n; x ++){
for(int y = 1; y <= m; y ++){
if(s[x][y] == char(i + '0')){
dp[i][i][x][y] = 0;
}
Pr = make_pair(x, y);
pq.push({dp[i][i][x][y], Pr});
mark[x][y] = 0;
}
}
BFS(i, i);
}
for(int len = 2; len <= k; len ++){
for(int l = 1, r = len; r <= k; l ++, r ++){
for(int x = 1; x <= n; x ++){
for(int y = 1; y <= m; y ++){
for(int mid = l; mid < r; mid ++){
dp[l][r][x][y] = min(dp[l][r][x][y], dp[l][mid][x][y] + dp[mid + 1][r][x][y]);
}
if(dp[l][r][x][y] < INF){
Pr = make_pair(x, y);
pq.push({dp[l][r][x][y], Pr});
mark[x][y] = 0;
}
}
}
BFS(l, r);
}
}
int ans = INF;
for(int x = 1; x <= n; x ++){
for(int y = 1; y <= m; y ++){
ans = min(ans, dp[1][k][x][y]);
}
}
cout << (ans == INF ? -1 : ans) << '\n';
return 0;
}
/*!
HE'S AN INSTIGATOR,
ENEMY ELIMINATOR,
AND WHEN HE KNOCKS YOU BETTER
YOU BETTER LET HIM IN.
*/
//! N.N
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
150252 KB |
Output is correct |
| 2 |
Correct |
93 ms |
150380 KB |
Output is correct |
| 3 |
Correct |
81 ms |
150252 KB |
Output is correct |
| 4 |
Correct |
81 ms |
150508 KB |
Output is correct |
| 5 |
Correct |
78 ms |
150380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
150252 KB |
Output is correct |
| 2 |
Correct |
93 ms |
150380 KB |
Output is correct |
| 3 |
Correct |
81 ms |
150252 KB |
Output is correct |
| 4 |
Correct |
81 ms |
150508 KB |
Output is correct |
| 5 |
Correct |
78 ms |
150380 KB |
Output is correct |
| 6 |
Correct |
83 ms |
150380 KB |
Output is correct |
| 7 |
Correct |
82 ms |
150252 KB |
Output is correct |
| 8 |
Correct |
82 ms |
150252 KB |
Output is correct |
| 9 |
Correct |
79 ms |
150380 KB |
Output is correct |
| 10 |
Correct |
80 ms |
150380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
150252 KB |
Output is correct |
| 2 |
Correct |
93 ms |
150380 KB |
Output is correct |
| 3 |
Correct |
81 ms |
150252 KB |
Output is correct |
| 4 |
Correct |
81 ms |
150508 KB |
Output is correct |
| 5 |
Correct |
78 ms |
150380 KB |
Output is correct |
| 6 |
Correct |
83 ms |
150380 KB |
Output is correct |
| 7 |
Correct |
82 ms |
150252 KB |
Output is correct |
| 8 |
Correct |
82 ms |
150252 KB |
Output is correct |
| 9 |
Correct |
79 ms |
150380 KB |
Output is correct |
| 10 |
Correct |
80 ms |
150380 KB |
Output is correct |
| 11 |
Correct |
368 ms |
153320 KB |
Output is correct |
| 12 |
Correct |
104 ms |
153320 KB |
Output is correct |
| 13 |
Correct |
190 ms |
153448 KB |
Output is correct |
| 14 |
Correct |
854 ms |
153448 KB |
Output is correct |
| 15 |
Correct |
297 ms |
153320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
150252 KB |
Output is correct |
| 2 |
Correct |
93 ms |
150380 KB |
Output is correct |
| 3 |
Correct |
81 ms |
150252 KB |
Output is correct |
| 4 |
Correct |
81 ms |
150508 KB |
Output is correct |
| 5 |
Correct |
78 ms |
150380 KB |
Output is correct |
| 6 |
Correct |
83 ms |
150380 KB |
Output is correct |
| 7 |
Correct |
82 ms |
150252 KB |
Output is correct |
| 8 |
Correct |
82 ms |
150252 KB |
Output is correct |
| 9 |
Correct |
79 ms |
150380 KB |
Output is correct |
| 10 |
Correct |
80 ms |
150380 KB |
Output is correct |
| 11 |
Correct |
368 ms |
153320 KB |
Output is correct |
| 12 |
Correct |
104 ms |
153320 KB |
Output is correct |
| 13 |
Correct |
190 ms |
153448 KB |
Output is correct |
| 14 |
Correct |
854 ms |
153448 KB |
Output is correct |
| 15 |
Correct |
297 ms |
153320 KB |
Output is correct |
| 16 |
Correct |
500 ms |
155876 KB |
Output is correct |
| 17 |
Execution timed out |
1531 ms |
155896 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
