第10回日本情報オリンピック 予選 C:チーズ

競技プログラミング

自力ACならず。

https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_e

普通の最短路問題とは違い、「Sからスタートして1まで行く」、「1からスタートして2まで行く」…という具合に始点と終点を切り替えながら複数回の幅優先探索をする必要がある。あとはそれぞれの探索における最短路を足し合わすことで、答えが得られる。

この発想ができず、なんかわけわからんフラグ管理とかして思考がぐちゃぐちゃになってしまった。dpとかでもそうだけど、漸化式をたてたり、以前までのターンの最適解はすでに計算されているものとして考える、っていう思考がまだまだ未熟。

あと迷路用のバッファを入力された数値ぴったり分確保していたら、延々とREを出してしまった。おれの頭では原因はわからない。

template <class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    } else {
        return false;
    }
}

int H, W, N;
vector<vector<char>> g_graph;
vector<vector<int>> g_distance;
const int dy[] = {-1, 0, 0, 1};
const int dx[] = {0, -1, 1, 0};
int g_x[10], g_y[10];

int ctoi(const char c) {
    if ('0' <= c && c <= '9')
        return (c - '0');
    return -1;
}

int bfs(const int sy, const int sx, const int gy, const int gx) {
    g_distance[sy][sx] = 0;
    queue<P> q;
    q.push(P(sy, sx));
    while (!q.empty()) {
        P now = q.front();
        q.pop();
        int y = now.first, x = now.second;
        if (y == gy && x == gx) {
            break;
        }

        rep(i, 4) {
            int ny = y + dy[i], nx = x + dx[i];
            if (ny < 0 || ny >= H || nx < 0 || nx >= W) {
                continue;
            }
            if (g_graph[ny][nx] == 'X') {
                continue;
            }

            bool update = chmin<int>(g_distance[ny][nx], g_distance[y][x] + 1);
            if (update) {
                q.push(P(ny, nx));
            }
        }
    }
    return g_distance[gy][gx];
}

signed main() {
    cin >> H >> W >> N;
    g_graph.assign(H + 10, vector<char>(W + 10));
    rep(i, H) {
        rep(j, W) {
            cin >> g_graph[i][j];
            if (g_graph[i][j] == 'S') {
                g_y[0] = i;
                g_x[0] = j;
            } else if (ctoi(g_graph[i][j]) != -1) {
                int n  = g_graph[i][j] - '0';
                g_y[n] = i;
                g_x[n] = j;
            }
        }
    }

    int ans = 0;
    rep(i, N) {
        g_distance.assign(H + 10, vector<int>(W + 10, INF));
        ans += bfs(g_y[i], g_x[i], g_y[i + 1], g_x[i + 1]);
    }
    cout << ans << endl;
}