This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define X first
#define Y second
#define MP make_pair
using namespace std;
const int inf = 1e5 + 1, N = 501;
int n, len, w, h, a[N][N], dp[10][10][N][N];
pair<int, int> end_pos[5][N][N];
queue< pair< pair<int, int>, pair<int, int> > > q;
void bfs(){
while(!q.empty()){
pair<int, int> pos = q.front().X, vals = q.front().Y;
q.pop();
if(vals.X + len <= n && vals.Y + 1 <= n)
dp[vals.X][vals.X + len][pos.X][pos.Y] = min(dp[vals.X][vals.X + len][pos.X][pos.Y], dp[vals.X][vals.Y][pos.X][pos.Y] + dp[vals.Y + 1][vals.X + len][pos.X][pos.Y]);
if(vals.Y - len >= 1 && vals.X - 1 >= 1)
dp[vals.Y - len][vals.Y][pos.X][pos.Y] = min(dp[vals.Y - len][vals.Y][pos.X][pos.Y], dp[vals.X][vals.Y][pos.X][pos.Y] + dp[vals.Y - len][vals.X - 1][pos.X][pos.Y]);
for(int i = 1;i <= 4;i++){
if(dp[vals.X][vals.Y][end_pos[i][pos.X][pos.Y].X][end_pos[i][pos.X][pos.Y].Y] > dp[vals.X][vals.Y][pos.X][pos.Y] + 1){
dp[vals.X][vals.Y][end_pos[i][pos.X][pos.Y].X][end_pos[i][pos.X][pos.Y].Y] = dp[vals.X][vals.Y][pos.X][pos.Y] + 1;
q.push(MP(end_pos[i][pos.X][pos.Y], vals));
}
}
}
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(dp, 0x3f, sizeof(dp));
cin >> n >> w >> h;
for(int i = 1;i <= h;i++){
for(int j = 1;j <= w;j++){
char x;
cin >> x;
if(x >= '0' && x <= '9'){
a[i][j] = x - '0';
dp[x - '0'][x - '0'][i][j] = 0;
q.push(MP(MP(i, j), MP(a[i][j], a[i][j])));
}
else if(x == 'x'){
a[i][j] = 13;
}
else if(x == 'A'){
a[i][j] = 11;
}
else if(x == 'C'){
a[i][j] = 12;
}
//cerr << a[i][j] << " ";
}
//cerr << "\n";
}
if(n == 1)
return cout << 0, 0;
for(int x = 1;x <= h;x++){
for(int y = 1;y <= w;y++){
if(a[x][y] == 13 || (x != 1 && x != h && y != 1 && y != w && a[x + 1][y] != 13 && a[x - 1][y] != 13 && a[x][y + 1] != 13 && a[x][y - 1] != 13))
continue;
for(int bdr = 1;bdr <= 4;bdr++){
pair<int, int> pos = MP(x, y);
int dr = bdr;
if(a[pos.X][pos.Y] == 12)
dr = (dr + 2) % 4 + 1;
else if(a[pos.X][pos.Y] == 11)
dr = dr % 4 + 1;
while(true){
if(dr == 1){
if(pos.X - 1 >= 1 && pos.X - 1 <= h && pos.Y >= 1 && pos.Y <= w && a[pos.X - 1][pos.Y] != 13)
pos.X -= 1;
else
break;
// cerr << pos.X << " " << pos.Y << "\n";
}
else if(dr == 2){
if(pos.X >= 1 && pos.X <= h && pos.Y - 1 >= 1 && pos.Y - 1 <= w && a[pos.X][pos.Y - 1] != 13)
pos.Y -= 1;
else
break;
}
else if(dr == 3){
if(pos.X + 1 >= 1 && pos.X + 1 <= h && pos.Y >= 1 && pos.Y <= w && a[pos.X + 1][pos.Y] != 13)
pos.X += 1;
else
break;
}
else{
if(pos.X >= 1 && pos.X <= h && pos.Y + 1 >= 1 && pos.Y + 1 <= w && a[pos.X][pos.Y + 1] != 13)
pos.Y += 1;
else
break;
}
if(a[pos.X][pos.Y] == 12)
dr = (dr + 2) % 4 + 1;
else if(a[pos.X][pos.Y] == 11)
dr = dr % 4 + 1;
if(end_pos[dr][pos.X][pos.Y] != MP(0, 0)){
pos = end_pos[dr][pos.X][pos.Y];
break;
}
//cerr << pos.X << " " << pos.Y << " " << x << " " << y << " " << dr << " " << bdr << " " << a[pos.X][pos.Y] << "\n";
}
end_pos[bdr][x][y] = pos;
//cerr << "was";
}
}
}
cerr << "was\n";
int ans = inf;
for(len = 1;len < n;len++){
bfs();
for(int A = 1, B = len + 1;B <= n;B++, A++){
for(int x = 1;x <= h;x++){
for(int y = 1;y <= w;y++){
if(dp[A][B][x][y] < inf && len != n - 1)
q.push(MP(MP(x, y), MP(A, B)));
if(len == n - 1 && A == 1 && B == n){
ans = min(ans, dp[A][B][x][y]);
}
}
}
}
}
if(ans >= inf)
ans = -1;
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |