#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int INF = 1e9;
int dp[9][9][505*505];
pii val[505][505][4];
int vis[505][505][4];
char board[505][505];
const pii mv[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int n, w, h;
pii add(pii a, pii b){ // ????
return make_pair(a.first + b.first, a.second + b.second);
}
bool check_wall(pii pos){
return board[pos.first][pos.second] == 'x' || board[pos.first][pos.second] == 'A' || board[pos.first][pos.second] == 'C';
}
vector<int> g[505*505];
pii dfs(pii pos, int d){
if(val[pos.first][pos.second][d].first)return val[pos.first][pos.second][d];
if(vis[pos.first][pos.second][d]){
val[pos.first][pos.second][d] = {-1, -1};
return {-1, -1};
}
vis[pos.first][pos.second][d] = 1;
auto old_pos = pos;
pos = add(pos, mv[d]);
while(!check_wall(pos))pos = add(pos, mv[d]);
if(board[pos.first][pos.second] == 'x')val[old_pos.first][old_pos.second][d] = add(pos, mv[d^2]);
else if(board[pos.first][pos.second] == 'C'){
val[old_pos.first][old_pos.second][d] = dfs(pos, d == 3 ? 0 : d + 1);
}
else {
val[old_pos.first][old_pos.second][d] = dfs(pos, d == 0 ? 3 : d - 1);
}
return val[old_pos.first][old_pos.second][d];
vis[old_pos.first][old_pos.second][d] = 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> h >> w;
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
for(int k = 0; k < w*h; k++)dp[i][j][k] = INF;
}
}
for(int i = 1; i <= w; i++){
for(int j = 1; j <= h; j++){
cin >> board[i][j];
if(board[i][j] >= '1' && board[i][j] <= '9')dp[board[i][j] - '1'][board[i][j]-'1'][(i-1)*h + (j-1)] = 0;
board[0][j] = board[w+1][j] = board[i][0] = board[i][h+1] = 'x';
}
}
for(int i = 1; i <= w; i++){
for(int j = 1; j <= h; j++){
if(board[i][j] == 'x')continue;
for(int k = 0; k < 4; k++){
pair<int, int> tmp = dfs(make_pair(i, j), k);
if(tmp.first != -1){
g[(i-1)*h + j - 1].push_back((tmp.first-1)*h + tmp.second - 1);
}
}
}
}
for(int len = 0; len < n; len++){
for(int l = 0; l + len < n; l++){
int r = l + len;
vector<pair<int, int>> inital;
for(int i = 0; i < w*h; i++){
for(int k = l; k < r; k++){
dp[l][r][i] = min(dp[l][r][i], dp[l][k][i] + dp[k+1][r][i]);
}
if(dp[l][r][i] < INF)inital.push_back({dp[l][r][i], i});
}
sort(inital.rbegin(), inital.rend());
queue<pair<int, int>> q;
while(!q.empty() || !inital.empty()){
pair<int, int> ele;
if(q.empty() || (!inital.empty() && inital.back().first < q.front().first)){
ele = inital.back();
inital.pop_back();
}
else {
ele = q.front();
q.pop();
}
if(len == n-1){
cout << ele.first+1-1;
return 0;
}
if(ele.first > dp[l][r][ele.second])continue;
for(auto v: g[ele.second]){
if(dp[l][r][v] > ele.first + 1){
dp[l][r][v] = ele.first+1;
q.push({ele.first+1, v});
}
}
}
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
12892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
12892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
12892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
12892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
