#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 5e2 + 1, lg = 9, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
int st[maxn][maxn], n, m, k;
pp ply[lg], adj[maxn][maxn][4];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool vis[maxn][maxn][4];
int dist[lg][lg][maxn][maxn];
pp dfs(int x, int y, int dir){
if(vis[x][y][dir]) return adj[x][y][dir];
adj[x][y][dir] = {-1, -1};
vis[x][y][dir] = true;
int d = dir;
if(st[x][y] == 2) d = (d + 3)%4;
if(st[x][y] == 3) d = (d + 1)%4;
int i = x + dx[d], j = y + dy[d];
if(i < 0 || i == n || j < 0 || j == m || !st[i][j]) return adj[x][y][dir] = {x, y};
return adj[x][y][dir] = dfs(i, j, d);
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
cin >> k >> m >> n;
rep(i,0,n) rep(j,0,m){
char c; cin >> c;
if(c == '.') st[i][j] = 1;
if(c == 'A') st[i][j] = 2;
if(c == 'C') st[i][j] = 3;
if(c >= '0' && c <= '9') st[i][j] = 1, ply[c-'1'] = {i, j};
}
rep(i,0,n) rep(j,0,m) rep(d,0,4) dfs(i, j, d);
rep(i,0,lg) rep(j,0,lg) rep(t,0,n) rep(f,0,m) dist[i][j][t][f] = inf;
rep(t,0,k){
deque<pp> q{ply[t]}; dist[t][t][ply[t].ff][ply[t].ss] = 0;
while(sz(q)){
auto[x, y] = q.front(); q.pop_front();
rep(d,0,4) if(adj[x][y][d].ff + 1 && dist[t][t][adj[x][y][d].ff][adj[x][y][d].ss] == inf){
q.push_back(adj[x][y][d]);
dist[t][t][adj[x][y][d].ff][adj[x][y][d].ss] = dist[t][t][x][y] + 1;
}
}
}
vector<vector<pp>> pos(k*n*m + 1);
rep(l,2,k+1){
rep(i,0,k-l+1){
int j = i + l - 1;
// priority_queue<pair<int, pp>, vector<pair<int, pp>>, greater<pair<int, pp>>> q;
rep(x,0,n) rep(y,0,m){
rep(m,i,j){
dist[i][j][x][y] = min(dist[i][j][x][y], dist[i][m][x][y] + dist[m+1][j][x][y]);
}
if(dist[i][j][x][y] - inf) pos[dist[i][j][x][y]].pb({x, y});
dist[i][j][x][y] = inf;
}
// while(sz(q)){
// auto[w, t] = q.top(); q.pop();
// auto[x, y] = t;
// if(w - dist[i][j][x][y]) continue;
// rep(d,0,4){
// auto[xp, yp] = adj[x][y][d];
// if(xp + 1 && dist[i][j][xp][yp] > w + 1){
// q.push({dist[i][j][xp][yp] = w + 1, {xp, yp}});
// }
// }
// }
rep(s,0,sz(pos)){
for(auto[x, y]: pos[s]) if(dist[i][j][x][y] == inf){
dist[i][j][x][y] = s;
rep(d,0,4) if(adj[x][y][d].ff + 1 && dist[i][j][adj[x][y][d].ff][adj[x][y][d].ss] == inf){
pos[s + 1].pb(adj[x][y][d]);
}
}
pos[s].clear();
}
}
}
int ans = inf;
rep(i,0,n) rep(j,0,m) ans = min(ans, dist[0][k-1][i][j]);
cout << (ans == inf? -1: ans) << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
724 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
724 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
1 ms |
724 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
1 ms |
980 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
724 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
1 ms |
724 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
1 ms |
980 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 11 |
Correct |
185 ms |
77508 KB |
Output is correct |
| 12 |
Correct |
40 ms |
55196 KB |
Output is correct |
| 13 |
Correct |
102 ms |
68440 KB |
Output is correct |
| 14 |
Correct |
266 ms |
80764 KB |
Output is correct |
| 15 |
Correct |
170 ms |
73292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
724 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
1 ms |
724 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
1 ms |
980 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 11 |
Correct |
185 ms |
77508 KB |
Output is correct |
| 12 |
Correct |
40 ms |
55196 KB |
Output is correct |
| 13 |
Correct |
102 ms |
68440 KB |
Output is correct |
| 14 |
Correct |
266 ms |
80764 KB |
Output is correct |
| 15 |
Correct |
170 ms |
73292 KB |
Output is correct |
| 16 |
Correct |
470 ms |
142708 KB |
Output is correct |
| 17 |
Runtime error |
431 ms |
163840 KB |
Execution killed with signal 9 |
| 18 |
Halted |
0 ms |
0 KB |
- |
