#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int N=505;
int n, m, k, u, v, x, y, t, a, b, ans;
char A[N][N];
pii nex[4][N][N];
bool mark[4][N][N];
int dp[10][10][N][N];
bool inq[N][N];
int DX[]={0, +1, 0, -1}, DY[]={+1, 0, -1, 0};
queue<pii> Q;
pii go(int dir, int x, int y){
// cerr<<"go "<<dir<<" "<<x<<", "<<y<<endl;
if (nex[dir][x][y]!=pii(0, 0)) return nex[dir][x][y];
if (mark[dir][x][y]) return nex[dir][x][y]={-1, -1};
mark[dir][x][y]=1;
int dd=dir;
if (A[x][y]=='A') dd=(dir+3)%4;
if (A[x][y]=='C') dd=(dir+1)%4;
int xx=x+DX[dd], yy=y+DY[dd];
if (!xx || xx>n || !yy || yy>m || A[xx][yy]=='x') return nex[dir][x][y]={x, y};
return nex[dir][x][y]=go(dd, xx, yy);
}
inline void upd(int& x, int y){ x=min(x, y);}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin>>k>>m>>n;
for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>>A[i][j];
for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) if (A[i][j]!='x')
for (int d:{0, 1, 2, 3}) go(d, i, j);
// hope nex is right
memset(dp, 63, sizeof(dp));
for (int l=k; l; l--) for (int r=l; r<=k; r++){
for (int x=1; x<=n; x++) for (int y=1; y<=m; y++){
if (l<r){
for (int i=l; i<r; i++) upd(dp[l][r][x][y], dp[l][i][x][y]+dp[i+1][r][x][y]);
}
else if (A[x][y]=='0'+l) upd(dp[l][r][x][y], 0);
}
// BFS or spfa
for (int x=1; x<=n; x++) for (int y=1; y<=m; y++) if (dp[l][r][x][y]<inf) Q.push({x, y});
while (Q.size()){
int x=Q.front().first, y=Q.front().second;
Q.pop();
inq[x][y]=0;
for (int d:{0, 1, 2, 3}) if (nex[d][x][y]!=pii(-1, -1)){
int xx=nex[d][x][y].first, yy=nex[d][x][y].second;
if (dp[l][r][x][y]+1<dp[l][r][xx][yy]){
dp[l][r][xx][yy]=dp[l][r][x][y]+1;
if (!inq[xx][yy]){
Q.push({xx, yy});
inq[xx][yy]=1;
}
}
}
}
}
ans=inf;
for (int x=1; x<=n; x++) for (int y=1; y<=m; y++) upd(ans, dp[1][k][x][y]);
if (ans>inf) ans=-1;
cout<<ans<<'\n';
return 0;
}
/*
2 2 2
C1
2C
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
100216 KB |
Output is correct |
| 2 |
Incorrect |
56 ms |
100216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
100216 KB |
Output is correct |
| 2 |
Incorrect |
56 ms |
100216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
100216 KB |
Output is correct |
| 2 |
Incorrect |
56 ms |
100216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
100216 KB |
Output is correct |
| 2 |
Incorrect |
56 ms |
100216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
