提出 #73388088

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1e18;
ll n;
struct Pt {
    ll r, c;
};
Pt get_pt(ll x) {
    return {(x - 1) / n + 1, (x - 1) % n + 1};
}
ll dist(Pt a, Pt b) {
    return abs(a.r - b.r) + abs(a.c - b.c);
}
ll dp[1 << 16][16];
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m;
    if (!(cin >> n >> m)) return 0;
    ll s_num, t_num;
    cin >> s_num >> t_num;
    Pt S = get_pt(s_num);
    Pt T = get_pt(t_num);
    if (m == 0) {
        cout << dist(S, T) << endl;
        return 0;
    }
    vector<Pt> p(m);
    for (int i = 0; i < m; i++) {
        ll x; cin >> x;
        p[i] = get_pt(x);
    }
    vector<vector<ll>> d(m, vector<ll>(m));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            d[i][j] = dist(p[i], p[j]);
        }
    }
    for (int i = 0; i < (1 << m); i++) {
        for (int j = 0; j < m; j++) {
            dp[i][j] = INF;
        }
    }

    for (int i = 0; i < m; i++) {
        dp[1 << i][i] = dist(S, p[i]);
    }
    for (int mask = 1; mask < (1 << m); mask++) {
        for (int i = 0; i < m; i++) {
            if (dp[mask][i] == INF) continue;
            for (int j = 0; j < m; j++) {
                if (!(mask & (1 << j))) {
                    dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + d[i][j]);
                }
            }
        }
    }
    ll ans = INF;
    int final_mask = (1 << m) - 1;
    for (int i = 0; i < m; i++) {
        ans = min(ans, dp[final_mask][i] + dist(p[i], T));
    }
    cout << ans << endl;
    return 0;
}

提出情報

ジャッジ結果