#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<bool> vb;
#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()
int w, h;
char G[500][500];
vector<vvi> vst(500, vvi(500, vi(4, -2)));
vector<vector<vvi>> dp(10, vector<vvi>(10, vvi(500, vi(500, 9999999))));
void cc(int r, int c, int d){
// d - 0 => up
// d - 1 => right
// d - 2 => down
// d - 3 => left
if(vst[r][c][d] != -2) return;
vst[r][c][d] = -1;
int d1 = d;
if(G[r][c] == 'C') d1++;
else if(G[r][c] == 'A') d1--;
d1 = (d1+4)%4;
int r1 = r, c1 = c;
if(d1 == 0) r1--;
else if(d1 == 1) c1++;
else if(d1 == 2) r1++;
else if(d1 == 3) c1--;
if(r1 < 0 || r1 >= h || c1 < 0 || c1 >= w || G[r1][c1] == 'x'){
vst[r][c][d] = r*w+c;
}else{
cc(r1, c1, d1);
vst[r][c][d] = vst[r1][c1][d1];
}
return;
}
struct node{
int r, c, cst;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n; cin >> n >> w >> h;
queue<node> cpc[10];
for(int r = 0; r < h; r++){
for(int c = 0; c < w; c++){
cin >> G[r][c];
int v = G[r][c]-'0';
if(0 < v && v < 10){
cpc[v].push({r, c, 0});
dp[v][v][r][c] = 0;
}
}
}
for(int r = 0; r < h; r++){
for(int c = 0; c < w; c++){
for(int d = 0; d < 4; d++){
cc(r, c, d);
}
}
}
for(int x = 1; x <= n; x++){
while(!cpc[x].empty()){
auto zx = cpc[x].front(); cpc[x].pop();
for(int d = 0; d < 4; d++){
int ww = vst[zx.r][zx.c][d];
if(ww < 0) continue;
int c = ww%w, r = (ww-c)/w;
if(zx.cst+1 < dp[x][x][r][c]){
dp[x][x][r][c] = zx.cst+1;
cpc[x].push({r, c, zx.cst+1});
}
}
}
}
for(int sz = 1; sz <= n; sz++){
for(int l = 1; l+sz <= n; l++){
queue<node> rpc;
for(int r = 0; r < h; r++){
for(int c = 0; c < w; c++){
for(int m = l; m < l+sz; m++){
int vvv = dp[l][m][r][c]+dp[m+1][l+sz][r][c];
dp[l][l+sz][r][c] = min(dp[l][l+sz][r][c], vvv);
}
if(dp[l][l+sz][r][c] < 9999999){
rpc.push({r, c, dp[l][l+sz][r][c]});
}
}
}
while(!rpc.empty()){
auto zx = rpc.front(); rpc.pop();
for(int d = 0; d < 4; d++){
int ww = vst[zx.r][zx.c][d];
if(ww < 0) continue;
int c = ww%w, r = (ww-c)/w;
if(zx.cst+1 < dp[l][l+sz][r][c]){
dp[l][l+sz][r][c] = zx.cst+1;
rpc.push({r, c, zx.cst+1});
}
}
}
}
}
int ans = INF;
for(int r = 0; r < h; r++)
for(int c = 0; c < w; c++)
ans = min(ans, dp[1][n][r][c]);
if(ans == INF) cout << -1 << endl;
else cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
124792 KB |
Output is correct |
| 2 |
Incorrect |
90 ms |
124792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
124792 KB |
Output is correct |
| 2 |
Incorrect |
90 ms |
124792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
124792 KB |
Output is correct |
| 2 |
Incorrect |
90 ms |
124792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
124792 KB |
Output is correct |
| 2 |
Incorrect |
90 ms |
124792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
