#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
const int INF = 1e9;
const int IIII = 1e6;
int n;
int w, h;
pair <int, int> nxt[MAXN][MAXN][4];
int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};
char a[MAXN][MAXN];
int dp[10][10][MAXN][MAXN];
vector <pair <int, int> > Pos[IIII];
pair <int, int> Cal(int i, int j, int dir)
{
// cout << i << ' ' << j << ' ' << dir << endl;
if(nxt[i][j][dir].first != -1)
{
return nxt[i][j][dir];
}
// cout << dir << endl;
int rdir = dir;
if(a[i][j] == 'A')
{
rdir++;
if(rdir == 4)
{
rdir = 0;
}
}
else if(a[i][j] == 'C')
{
rdir--;
if(rdir == -1)
{
rdir = 3;
}
}
// cout << rdir << endl;
int nx = i + dx[rdir], ny = j + dy[rdir];
nxt[i][j][dir] = make_pair(-2, -2);
if(nx == 0 or nx == h + 1 or ny == 0 or ny == w + 1)
{
return nxt[i][j][dir] = make_pair(i, j);
}
if(a[nx][ny] == 'x')
{
return nxt[i][j][dir] = make_pair(i, j);
}
return nxt[i][j][dir] = Cal(nx, ny, rdir);
}
int main()
{
// freopen("Input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> w >> h;
for(int i = 1; i <= h; i++)
{
for(int j = 1; j <= w; j++)
{
cin >> a[i][j];
}
}
for(int i = 1; i <= h; i++)
{
for(int j = 1; j <= w; j++)
{
for(int k = 0; k < 4; k++)
{
nxt[i][j][k] = make_pair(-1, -1);
}
}
}
for(int i = 1; i <= h; i++)
{
for(int j = 1; j <= w; j++)
{
for(int k = 0; k < 4; k++)
{
if(a[i][j] != 'x')
{
Cal(i, j, k);
// cout << i << ' ' << j << ' ' << k << '\n';
// cout << nxt[i][j][k].first << ' ' << nxt[i][j][k].second << '\n';
}
}
}
}
for(int diff = 0; diff < n; diff++)
{
for(int vx = 1; vx + diff <= n; vx++)
{
int vy = vx + diff;
int tmp = 1e9;
if(diff == 0)
{
for(int i = 1; i <= h; i++)
{
for(int j = 1; j <= w; j++)
{
if(a[i][j] - '0' == vx)
{
dp[vx][vy][i][j] = 0;
Pos[0].emplace_back(i, j);
tmp = 0;
}
else
{
dp[vx][vy][i][j] = INF;
}
}
}
}
else
{
for(int i = 1; i <= h; i++)
{
for(int j = 1; j <= w; j++)
{
dp[vx][vy][i][j] = INF;
for(int k = vx; k < vy; k++)
{
dp[vx][vy][i][j] = min(dp[vx][vy][i][j], dp[vx][k][i][j] + dp[k + 1][vy][i][j]);
}
if(dp[vx][vy][i][j] != INF)
{
Pos[dp[vx][vy][i][j]].emplace_back(i, j);
tmp = min(tmp, dp[vx][vy][i][j]);
}
}
}
}
for(int vv = tmp; vv < tmp + MAXN * MAXN; vv++)
{
while(!Pos[vv].empty())
{
int x = Pos[vv].back().first, y = Pos[vv].back().second;
Pos[vv].pop_back();
if(dp[vx][vy][x][y] == vv)
{
for(int dir = 0; dir < 4; dir++)
{
int nx = nxt[x][y][dir].first, ny = nxt[x][y][dir].second;
if(nx >= 1 and nx <= h and ny >= 1 and ny <= w)
{
if(dp[vx][vy][nx][ny] > vv + 1)
{
dp[vx][vy][nx][ny] = vv + 1;
Pos[vv + 1].emplace_back(nx, ny);
}
}
}
}
}
}
}
}
int ans = INF;
for(int i = 1; i <= h; i++)
{
for(int j = 1; j <= w; j++)
{
ans = min(ans, dp[1][n][i][j]);
}
}
if(ans == INF)
{
ans = -1;
}
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23756 KB |
Output is correct |
| 2 |
Runtime error |
35 ms |
48032 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23756 KB |
Output is correct |
| 2 |
Runtime error |
35 ms |
48032 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23756 KB |
Output is correct |
| 2 |
Runtime error |
35 ms |
48032 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23756 KB |
Output is correct |
| 2 |
Runtime error |
35 ms |
48032 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
