/* In the name of Allah */
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int inf = 9;
int n, w, h;
string grid[510];
int hsh[10][10], dp[50][510][510];
bool vis[4][510][510];
pair < int, int > nxt[4][510][510];
pair < int, int > dirs[4] = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} };
bool ok( int x, int y ){
return( 0 <= x && x < h && 0 <= y && y < w && grid[x][y] != 'x');
}
/*
nxt[d][x][y] = {-1, -1} -> nxt[d][x][y] is not calculated yet;
nxt[d][x][y] = {-2, -2} -> nxt[d][x][y] is not defined. There are a infinite loop;
nxt[d][x][y] is not in {{-2, -2} {-1, -1}} -> nxt[d][x][y] is calculated.
*/
pair < int, int > rec(int d, int x, int y){
if( nxt[d][x][y] != make_pair(-1, -1) )return nxt[d][x][y];
if( vis[d][x][y] ) return nxt[d][x][y] = {-2, -2};
vis[d][x][y] = 1;
int dd = d;
if( grid[x][y] == 'A' )if( --dd < 0 ) dd += 4;
if( grid[x][y] == 'C' )if( ++dd > 3 ) dd -= 4;
int xx = x + dirs[dd].x, yy = y + dirs[dd].y;
if( ok(xx, yy) ) return nxt[d][x][y] = rec( dd, xx, yy );
return nxt[d][x][y] = {x,y};
}
void bfs( int id, priority_queue < vector < int > > q){
while( !q.empty() ){
auto fr = q.top(); q.pop();
int cost = -fr[0], x = fr[1], y = fr[2];
if( cost != dp[id][x][y] ) continue;
for( int d = 0; d < 4; d ++ ){
auto to = nxt[d][x][y];
if( to != make_pair(-2, -2) && dp[id][x][y] + 1 < dp[id][to.x][to.y] ){
dp[id][to.x][to.y] = dp[id][x][y] + 1;
q.push({-dp[id][to.x][to.y], to.x, to.y});
}
}
}
}
int main(){
cin >> n >> w >> h;
for( int i = 0; i < h; i ++ )
cin >> grid[i];
int cnt = 0;
for( int i = 0; i < n; i ++ ){
for( int j = i+1; j <= n; j ++ ){
hsh[i][j] = cnt++;
}
}
for( int i = 0; i < h; i ++ ){
for( int j = 0; j < w; j ++ ){
for( int d = 0; d < 4; d ++ ){
nxt[d][i][j] = {-1, -1};
}
}
}
for( int i = 0; i < h; i ++ ){
for( int j = 0; j < w; j ++ ){
for( int d = 0; d < 4; d ++ ){
rec(d, i, j);
}
}
}
for( int i = 0; i < h; i ++ ){
for( int j = 0; j < w; j ++ ){
for( int id = 0; id < cnt; id ++ ){
dp[id][i][j] = inf;
}
}
}
for( int id = 0; id < n; id ++ ){
for( int i = 0; i < h; i ++ ){
for( int j= 0; j < w; j ++ ){
if( grid[i][j] == id + 49 ){
dp[hsh[id][id+1]][i][j] = 0;
priority_queue < vector < int > > pq;
pq.push({0, i, j} );
bfs(hsh[id][id+1], pq);
}
}
}
}
for( int len = 2; len <= n ; len ++ ){
for( int i = 0; i <= n - len; i ++ ){
int j = i + len;
priority_queue < vector < int > > pq;
for( int x = 0; x < h; x ++ ){
for( int y = 0; y < w; y ++ ){
for( int k = i+1; k < j; k ++ ){
if( dp[hsh[i][j]][x][y] > dp[hsh[i][k]][x][y] + dp[hsh[k][j]][x][y] ){
dp[hsh[i][j]][x][y] = dp[hsh[i][k]][x][y] + dp[hsh[k][j]][x][y];
}
}
if( dp[hsh[i][j]][x][y] != inf ) pq.push({-dp[hsh[i][j]][x][y], x, y});
}
}
bfs(hsh[i][j], pq);
}
}/*
for( int d = 0; d < 4; d ++ ){
cout << "----> " << d << endl;
for( int i = 0; i < h; i ++ ){
for( int j = 0; j < w; j ++ ){
cout << nxt[d][i][j].x << ' ' << nxt[d][i][j].y << " " ;
}cout << endl;
}
}
for( int i = 0; i < n; i ++ ){
for( int j = i+1; j <= n; j ++ ){
cout << "----> " << i << ' ' << j << endl;
for( int x = 0; x < h; x ++ ){
for( int y = 0; y < w; y ++ ){
cout << dp[hsh[i][j]][x][y] << ' ';
}cout << endl;
}
}
}*/
int res = inf;
for( int x = 0; x < h; x ++ ){
for( int y = 0; y < w; y ++ ){
res = min( res, dp[hsh[0][n]][x][y] );
}
}
if( res == inf ) cout << -1;
else cout << res;
}
/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
572 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
572 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
572 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
572 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
