// #pragma optimize ("g",on)
// #pragma GCC optimize("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
#include <bits/stdc++.h>
#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0);
#define bitcount(n) __builtin_popcountll(n)
#define puts(x) (x ? "YES\n" : "NO\n");
#define ent (i == n ? '\n' : ' ')
#define all(x) x.begin(), x.end()
#define md ((l + r) >> 1)
#define rv(v) ((v << 1) | 1)
#define lv(v) (v << 1)
#define rs(v) rv(v), md + 1, r
#define ls(v) lv(v), l, md
#define len(s) (int) s.size()
#define pb push_back
#define S second
#define F first
// #define int long long
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector < ll > vll;
typedef pair < ll, ll > pll;
typedef vector < pair < ll, ll > > vpll;
const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int N = 5e2 + 23;
const int K = 2e5;
const int mod = 998244353;
const ll inf = 1e9 + 10;
//mt19937 rnd(07062006);
ll k, n, m, res, cur, cnt;
ll d[10][N][N], ans[10][10][N][N];
pll was[N][N][2][2][2][2], pos[N];
char a[N][N];
bool good(ll x, ll y){
return x >= 1 && y >= 1 && x <= n && y <= m && a[x][y] != 'x';
}
void move(ll &x, ll &y, ll d1, ll d2, ll d3, ll d4){
ll X = x, Y = y;
vector < vll > v;
v.pb({x, y, d1, d2, d3, d4});
while(1){
// cout << x << ' ' << y << '\n';
if(a[x][y] == 'C'){
if(d1) d1 = 0, d2 = 1;
else if(d2) d2 = 0, d3 = 1;
else if(d3) d3 = 0, d4 = 1;
else d4 = 0, d1 = 1;
}
if(a[x][y] == 'A'){
if(d1) d1 = 0, d4 = 1;
else if(d2) d2 = 0, d1 = 1;
else if(d3) d3 = 0, d2 = 1;
else d4 = 0, d3 = 1;
}
if(d1) y++;
else if(d2) x++;
else if(d3) y--;
else x--;
if(!good(x, y)) break;
v.pb({x, y, d1, d2, d3, d4});
}
x = v[len(v) - 1][0], y = v[len(v) - 1][1];
if(!was[v[len(v) - 1][0]][v[len(v) - 1][1]][v[len(v) - 1][2]][v[len(v) - 1][3]][v[len(v) - 1][4]][v[len(v) - 1][5]].F){
was[v[len(v) - 1][0]][v[len(v) - 1][1]][v[len(v) - 1][2]][v[len(v) - 1][3]][v[len(v) - 1][4]][v[len(v) - 1][5]] = {x, y};
}
for(auto it : v) was[it[0]][it[1]][it[2]][it[3]][it[4]][it[5]] = was[v[len(v) - 1][0]][v[len(v) - 1][1]][v[len(v) - 1][2]][v[len(v) - 1][3]][v[len(v) - 1][4]][v[len(v) - 1][5]] = {x, y};
// for(auto it : v) cout << it[0] << ' ' << it[1] << '\n';
// cout << x << ' ' << y << ' ' << d[1][x][y] << '\n';
}
void bfs(pll s, ll id){
ll x, y;
queue < pll > q;
for(ll i = 1; i <= n; i++)
for(ll j = 1; j <= m; j++)
d[id][i][j] = inf;
for(ll i = 1; i <= n; i++)
for(ll j = 1; j <= m; j++)
for(ll d1 = 0; d1 <= 1; d1++)
for(ll d2 = 0; d2 <= 1; d2++)
for(ll d3 = 0; d3 <= 1; d3++)
for(ll d4 = 0; d4 <= 1; d4++)
was[i][j][d1][d2][d3][d4] = {0, 0};
q.push(s), d[id][s.F][s.S] = 0;
while(len(q)){
auto [X, Y] = q.front();
q.pop();
x = X, y = Y, move(x, y, 0, 0, 0, 1);
if(good(x, y) && d[id][X][Y] + 1 < d[id][x][y]){
d[id][x][y] = d[id][X][Y] + 1;
q.push({x, y});
}
x = X, y = Y, move(x, y, 0, 0, 1, 0);
if(good(x, y) && d[id][X][Y] + 1 < d[id][x][y]){
d[id][x][y] = d[id][X][Y] + 1;
q.push({x, y});
}
x = X, y = Y, move(x, y, 0, 1, 0, 0);
if(good(x, y) && d[id][X][Y] + 1 < d[id][x][y]){
d[id][x][y] = d[id][X][Y] + 1;
q.push({x, y});
}
x = X, y = Y, move(x, y, 1, 0, 0, 0);
if(good(x, y) && d[id][X][Y] + 1 < d[id][x][y]){
d[id][x][y] = d[id][X][Y] + 1;
q.push({x, y});
}
}
// exit(0);
}
void output(){
cin >> k >> m >> n, res = inf;
for(ll i = 1; i <= n; i++)
for(ll j = 1; j <= m; j++)
cin >> a[i][j];
for(ll i = 1; i <= n; i++)
for(ll j = 1; j <= m; j++)
if('1' <= a[i][j] && a[i][j] <= '9')
pos[a[i][j] - '0'] = {i, j}, bfs({i, j}, a[i][j] - '0');
for(ll i = 1; i <= n; i++){
for(ll j = 1; j <= m; j++){
for(ll id1 = k; id1 >= 1; id1--){
for(ll id2 = id1; id2 <= k; id2++){
if(id1 == id2){
ans[id1][id2][i][j] = d[id1][i][j];
}
else{
ans[id1][id2][i][j] = min(ans[id1 + 1][id2][i][j] + d[id1][i][j], ans[id1][id2 - 1][i][j] + d[id2][i][j]);
}
}
}
res = min(res, ans[1][k][i][j]);
}
}
cout << res;
}
const bool cases = 0;
signed main(){
// file("disrupt");
adiyer();
int tt = 1;
if(cases) cin >> tt;
for(int i = 1; i <= tt; i++){
output();
}
}
Compilation message
robots.cpp: In function 'void move(ll&, ll&, ll, ll, ll, ll)':
robots.cpp:58:5: warning: unused variable 'X' [-Wunused-variable]
58 | ll X = x, Y = y;
| ^
robots.cpp:58:12: warning: unused variable 'Y' [-Wunused-variable]
58 | ll X = x, Y = y;
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
12752 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
12752 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
12752 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
12752 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
