이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define X first
#define Y second
#define MP make_pair
using namespace std;
const int inf = 250000, N = 500;
char a[N][N];
int n, w, h, dp[9][9][N][N];
pair<int, int> end_pos[4][N][N];
vector< pair<int, int> > q[inf];
vector< pair< int, pair< int, int > > > temp;
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 = 0;i < h;i++){
for(int j = 0;j < w;j++){
cin >> a[i][j];
if(a[i][j] >= '0' && a[i][j] <= '9'){
dp[a[i][j] - '0' - 1][a[i][j] - '0' - 1][i][j] = 0;
}
}
}
for(int x = 0;x < h;x++){
for(int y = 0;y < w;y++){
if(a[x][y] == 'x')
continue;
for(int d = 0;d < 4;d++){
int dr = d;
if(a[x][y] == 'A')
dr = (dr + 3) % 4;
else if(a[x][y] == 'C')
dr = (dr + 1) % 4;
pair<int, int> pos = MP(x, y);
while(true){
if(dr == 0){
if(pos.X - 1 >= 0 && pos.X - 1 < h && pos.Y >= 0 && pos.Y < w && a[pos.X - 1][pos.Y] != 'x')
pos.X -= 1;
else
break;
}
else if(dr == 3){
if(pos.X >= 0 && pos.X < h && pos.Y - 1 >= 0 && pos.Y - 1 < w && a[pos.X][pos.Y - 1] != 'x')
pos.Y -= 1;
else
break;
}
else if(dr == 2){
if(pos.X + 1 >= 0 && pos.X + 1 < h && pos.Y >= 0 && pos.Y < w && a[pos.X + 1][pos.Y] != 'x')
pos.X += 1;
else
break;
}
else if(dr == 1){
if(pos.X >= 0 && pos.X < h && pos.Y + 1 >= 0 && pos.Y + 1 < w && a[pos.X][pos.Y + 1] != 'x')
pos.Y += 1;
else
break;
}
if(end_pos[dr][pos.X][pos.Y] != MP(0, 0)){
pos = end_pos[dr][pos.X][pos.Y];
break;
}
else{
temp.push_back(MP(dr, pos));
}
if(a[pos.X][pos.Y] == 'A')
dr = (dr + 3) % 4;
else if(a[pos.X][pos.Y] == 'C')
dr = (dr + 1) % 4;
}
end_pos[d][x][y] = pos;
while(!temp.empty()){
end_pos[temp.back().X][temp.back().Y.X][temp.back().Y.Y] = pos;
temp.pop_back();
}
}
}
}
int ans = inf;
for(int len = 1;len < n;len++){
for(int A = 0;A + len - 1 < n;A++){
int B = A + len - 1;
for(int x = 0;x < h;x++){
for(int y = 0;y < w;y++){
if(a[x][y] != 'x' && dp[A][B][x][y] < inf){
q[dp[A][B][x][y]].push_back(MP(x, y));
}
}
}
for(int it = 0;it < inf;it++){
for(pair<int, int> pos: q[it]){
for(int dr = 0;dr < 4;dr++){
pair<int, int> to = end_pos[dr][pos.X][pos.Y];
if(dp[A][B][pos.X][pos.Y] + 1 < dp[A][B][to.X][to.Y]){
dp[A][B][to.X][to.Y] = dp[A][B][pos.X][pos.Y] + 1;
if(it + 1 < inf)
q[it + 1].push_back(to);
}
}
}
q[it].clear();
}
}
for(int A = 0;A + len < n;A++){
int B = A + len;
for(int x = 0;x < h;x++){
for(int y = 0;y < w;y++){
if(a[x][y] != 'x'){
for(int C = A;C < B;C++){
dp[A][B][x][y] = min(dp[A][B][x][y], dp[A][C][x][y] + dp[C + 1][B][x][y]);
}
}
}
}
}
}
/*
cerr << end_pos[0][3][0].X << " " << end_pos[0][3][0].Y << "\n";
cerr << dp[1][1][1][0] << "\n"; */
for(int x = 0;x < h;x++){
for(int y = 0;y < w;y++){
if(a[x][y] != 'x')
ans = min(ans, dp[0][n - 1][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... |