---
tags: APIO
---
# APIO 2013-1 Robots

重実装つらい

## 問題文

https://oj.uz/problem/view/APIO13_robots

2次元グリッド上に $1$ 〜 $N$ のロボットがあります。
ロボットは動かすと壁か外枠に当たるまで進み続けます。
また、グリッド上に回転板があり、ロボットが上を通ると指定された向きに90°進行方向が変わります。
ロボットは重なることができ、連続する番号のロボットが(停止して)重なっているとき、連結して1つのロボットになります。
全てのロボットを連結するのに必要な操作回数を求めてください。
$H, W ≤ 500$
$2 ≤ N ≤ 9$

## 考察

2次元グリッドを有向グラフに変換して考えてみる。

(ロボット 1-2 を作るコスト) $= \min_{i,j}$ (ロボット 1 を $(i, j)$ に移動するコスト) + (ロボット 2 を $(i, j)$ に移動するコスト)

(ロボット 1-3 を作るコスト) $=$ $\min($
$\min_{i,j}$ (ロボット 1 を $(i, j)$ に移動するコスト) + (ロボット 2-3 を $(i, j)$ に移動するコスト),
$\min_{i,j}$ (ロボット 1-2 を $(i, j)$ に移動するコスト) + (ロボット 3 を $(i, j)$ に移動するコスト)
$)$

ロボット 1-2 を $(i, j)$ に移動するコストを求めるには、
- BFSでロボット 1 を $(i, j)$ に移動するコストを求める
- BFSでロボット 2 を $(i, j)$ に移動するコストを求める
- 足し算でロボット 1-2 を $(i, j)$ で作るコストを求める
- Dijkstraでロボット 1-2 を $(i, j)$ に移動するコストを求める

これを全てのロボットの連結に対して区間DPっぽく求めればいい。

## 実装

2次元グリッドを有向グラフに変換するのがまず大変
TLがかなりきついので、 priority_queue による Dijkstra を 事前ソートして BFS に変更すると通る

867ms / 1500ms
https://oj.uz/submission/235329

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using tuplis = array<int, 3>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
#define overload4(_1,_2,_3,_4,name,...) name
#define rep1(n) for(int i=0;i<n;++i)
#define rep2(i,n) for(int i=0;i<n;++i)
#define rep3(i,a,b) for(int i=a;i<b;++i)
#define rep4(i,a,b,c) for(int i=a;i<b;i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)
template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int INF = 0x33333333;
 
 
int n, w, h;
pii mem[500][500][4];
char s[501][501];
vector<pii> g[500][500];
int cost[10][10][500][500];
pii dfs(int x, int y, int d){
    if(x < 0) return {x + 1, y};
    if(y < 0) return {x, y + 1};
    if(x >= h) return {x - 1, y};
    if(y >= w) return {x, y - 1};
    if(s[x][y] == 'x') return {x + dx[d ^ 2], y + dy[d ^ 2]};
    if(mem[x][y][d] != pii{-1, -1}) return mem[x][y][d];
    int d2 = d;
    if(s[x][y] == 'A'){
        d2 += 3;
        d2 &= 3;
    }
    else if(s[x][y] == 'C'){
        d2 += 1;
        d2 &= 3;
    }
    mem[x][y][d] = {-2, -2};
    return mem[x][y][d] = dfs(x + dx[d2], y + dy[d2], d2);
}
void bfs(int from, int to){
    auto c = cost[from][to];
    rep(cen, from + 1, to) rep(h) rep(j, w) chmin(c[i][j], cost[from][cen][i][j] + cost[cen][to][i][j]);
    queue<tuplis> q;
    vector<tuplis> q2;
    rep(h) rep(j, w) if(c[i][j] != INF) q2.push_back({c[i][j], i, j});
    sort(all(q2), greater<tuplis>());
    while(q.size() || q2.size()){
        bool flag = 0;
        if(!q2.size()) flag = 1;
        else if(q.size() && q.front()[0] < q2.back()[0]) flag = 1;
        auto [cost, x, y] = flag ? q.front() : q2.back();
        if(flag) q.pop();
        else q2.pop_back();
        for(auto [x2, y2] : g[x][y]) if(chmin(c[x2][y2], cost + 1)){
            q.push({c[x2][y2], x2, y2});
        }
    }
}
int main(){
    memset(mem, 0xff, sizeof(mem));
    memset(cost, 0x33, sizeof(cost));
    scanf("%d%d%d", &n, &w, &h);
    rep(h) scanf("%s", s[i]);
    rep(h) rep(j, w) rep(d, 4) dfs(i, j, d);
    rep(h) rep(j, w) rep(d, 4) if(mem[i][j][d] != pii{-2, -2} && mem[i][j][d] != pii{i, j}) g[i][j].push_back(mem[i][j][d]);
    rep(h) rep(j, w) if(isdigit(s[i][j]))cost[s[i][j] - '1'][s[i][j] - '0'][i][j] = 0;
    rep(i, 1, n + 1) rep(j, 0, n + 1 - i) bfs(j, j + i);
    int ans = INF;
    rep(h) rep(j, w) chmin(ans, cost[0][n][i][j]);
    if(ans == INF) ans = -1;
    printf("%d\n", ans);
}