JOI 二次予選 2020 D - テンキー (AOJ 0675, 難易度 7)

本選参加のボーダーとなった問題らしい！それにしても JOI は実装が重たい...！！！

問題へのリンク

類題とか

drken1215.hatenablog.com

問題概要

初期状態では下図のようなテンキーの「0」のところにカーソルがある。

• 上下左右への移動
• ボタンを押す (315 に 4 を押すと 3154 になる)

を最小回数繰り返して、 で割って あまる状態にせよ。

制約

• 

考えたこと

一般に、あることを実現するための最小回数を求めるためには、探索空間が十分に小さければ BFS でできる。今回もそんな感じ。探索空間としては

• (i, j, r)： マス (i, j) にカーソルがあって、できている数を M で割ったあまりが r であるような状態

としてあげて、

• dist[ i ][ j ][ r ] := 上記状態にするまでの最小回数

として BFS すれば良さそう。計算量は単純に になる。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using pint = pair<int,int>;
using Node = pair<pint,int>;
const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};

vector<vector<int>> val = {vector<int>({7, 8, 9}),
    vector<int>({4, 5, 6}), vector<int>({1, 2, 3}), vector<int>({0})};

int dp[5][5][210000];
int main() {
    int M, R;
    cin >> M >> R;
    memset(dp, -1, sizeof(dp));
    dp[3][0][0] = 0;
    queue<Node> que;
    que.push(Node(pint(3, 0), 0));
    while (!que.empty()) {
        auto cur = que.front(); que.pop();
        int x = cur.first.first, y = cur.first.second;
        int r = cur.second;
        {
            int nr = (r * 10 + val[x][y]) % M;
            if (dp[x][y][nr] == -1) {
                dp[x][y][nr] = dp[x][y][r] + 1;
                que.push(Node(pint(x, y), nr));
            }
        }
        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if (nx < 0 || nx >= 4 || ny < 0 || ny >= val[nx].size()) continue;
            if (dp[nx][ny][r] == -1) {
                dp[nx][ny][r] = dp[x][y][r] + 1;
                que.push(Node(pint(nx, ny), r));
            }
        }
    }
    int res = 1<<29;
    for (int x = 0; x < 4; ++x) {
        for (int y = 0; y < val[x].size(); ++y) {
            chmin(res, dp[x][y][R]);
        }
    }
    cout << res << endl;
}