#include <iostream>
#include <bits/stdc++.h>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <iomanip>
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
//#define int long long
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
using namespace std;
const int H = 501;
string m[H];
int dp[H][H][10][10];
pair<int, int> final[H][H][4];
vector<pair<int, int>> adj[H][H];
int n, h, w;
int A(int x){
return ((x+1)%4);
}
int C(int x){
return ((x-1+4)%4);
}
bool valid(pair<int, int> x){
if(x.first < 0 || x.second<0) return false;
if(x.first >= h || x.second >= w) return false;
return m[x.first][x.second] != 'x';
}
pair<int, int> update(pair<int, int> x, int dir){
if(dir==0){
x.first++;
return x;
}
if(dir==1){
x.second++;
return x;
}
if(dir==2){
x.first--;
return x;
}
x.second--;
return x;
}
pair<int, int> nxt(pair<int, int> curr, int &dir){
if(m[curr.first][curr.second]=='C') dir = C(dir);
else if(m[curr.first][curr.second]=='A') dir = A(dir);
if(!valid(update(curr, dir))) return curr;
return update(curr, dir);
}
pair<int, int> dfs(int i, int j, int dir){
if(final[i][j][dir].first >=0){
return final[i][j][dir];
}
else if(final[i][j][dir].first==-1){
return {-1, -1};
}
final[i][j][dir] = {-1, -1};
int currd = dir;
pair<int, int> togo = nxt({i, j}, dir);
if(togo.first == i && togo.second == j){
//cout<<i<<" "<<j<<" in direction "<<dir<<" can't move"<<endl;
return final[i][j][currd] = {i, j};
}
final[i][j][currd] = dfs(togo.first, togo.second, dir);
//cout<<i<<" "<<j<<" in direction "<<currd<<" leads to "<<final[i][j][currd].first<<" "<<final[i][j][currd].second<<endl;
return final[i][j][currd];
}
void BFS(pair<int, int> curr, int st){
for(int i =0 ;i<h;i++){
for(int j = 0;j<w;j++) dp[i][j][st][st] = INF;
}
dp[curr.first][curr.second][st][st] = 0;
queue<pair<int, int>> q;
q.push(curr);
while(!q.empty()){
curr = q.front();
q.pop();
for(pair<int, int> k: adj[curr.first][curr.second]){
if(dp[k.first][k.second][st][st] < INF) continue;
dp[k.first][k.second][st][st] = dp[curr.first][curr.second][st][st] + 1;
q.push(k);
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>w>>h;
for(int i =0 ;i<h;i++) cin>>m[i];
//dir 0 -> i++
//dir 1 -> j++
//dir 2 -> i--
//dir 3 -> j--
for(int i =0 ;i<h;i++){
for(int j =0 ;j<w;j++){
for(int k = 0;k<4;k++) final[i][j][k] = {-2, -2};
}
}
for(int i = 0;i<h;i++){
for(int j = 0;j<w;j++){
for(int k = 0;k<4;k++){
if(m[i][j]=='x') continue;
pair<int, int> ta = dfs(i, j, k);
//cout<<i<<" "<<j<<" "<<k<<" leads to ("<<ta.first<<", "<<ta.second<<")"<<endl;
if(ta.first != -1){
adj[i][j].push_back(ta);
}
}
}
}
for(int i = 0;i<h;i++){
for(int j = 0;j<w;j++){
if(m[i][j]=='A' || m[i][j]=='C' || m[i][j]=='x' || m[i][j]=='.') continue;
int curr = m[i][j] - '0';
BFS({i, j}, curr);
}
}
vector<pair<int, int>> dPush[50000];
for(int sz = 1;sz<n;sz++){
for(int st = 1;(st+sz)<=n;st++){
int sd = (st+sz);
pair<int, int> toPush;
int minCost = INF;
for(int i =0 ;i<h;i++){
for(int j = 0;j<w;j++){
dp[i][j][st][sd] = INF;
for(int k = st;k<sd;k++) dp[i][j][st][sd] = min(dp[i][j][st][k] + dp[i][j][k+1][sd], dp[i][j][st][sd]);
if(dp[i][j][st][sd] < INF){
minCost = min(minCost, dp[i][j][st][sd]);
dPush[dp[i][j][st][sd]].push_back({i, j});
}
}
}
if(minCost == INF) continue;
queue<pair<int, int>> q;
for(pair<int, int> j: dPush[minCost]) q.push({j.first, j.second});
dPush[minCost].clear();
while(!q.empty()){
pair<int, int> curr = q.front();
q.pop();
int i = curr.first, j = curr.second;
int cd = dp[i][j][st][sd];
for(pair<int, int> nxt: dPush[cd+1]){
if(dp[nxt.first][nxt.second][st][sd] < (cd+1)) continue;
dp[nxt.first][nxt.second][st][sd] = cd + 1;
q.push(nxt);
}
dPush[cd+1].clear();
for(pair<int, int> nxt: adj[i][j]){
if(dp[nxt.first][nxt.second][st][sd] <= (cd+1)) continue;
dp[nxt.first][nxt.second][st][sd] = cd + 1;
q.push({nxt.first, nxt.second});
}
}
for(int i =0 ;i<h;i++){
for(int j = 0;j<w;j++){
int k = INF;
for(int kk = st;kk<sd;kk++) k = min(dp[i][j][st][kk] + dp[i][j][kk+1][sd], k);
if(k<INF) dPush[k].clear();
}
}
}
}
int ans = INF;
for(int i =0 ;i<h;i++){
for(int j =0;j<w;j++){
ans = min(ans, dp[i][j][1][n]);
}
}
if(ans >= INF) ans = -1;
cout<<ans<<endl;
}
/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7552 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7552 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7552 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 9 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 10 |
Correct |
4 ms |
7552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7552 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7552 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 9 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 10 |
Correct |
4 ms |
7552 KB |
Output is correct |
| 11 |
Runtime error |
289 ms |
106360 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7552 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7552 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 9 |
Correct |
4 ms |
7424 KB |
Output is correct |
| 10 |
Correct |
4 ms |
7552 KB |
Output is correct |
| 11 |
Runtime error |
289 ms |
106360 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
