QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#742719#3128. Rush Hour Puzzleucup-team5226#AC ✓330ms29404kbC++203.2kb2024-11-13 17:09:062024-11-13 17:09:07

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 17:09:07]
  • 评测
  • 测评结果:AC
  • 用时:330ms
  • 内存:29404kb
  • [2024-11-13 17:09:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
const ll INF = LLONG_MAX / 4;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vc<vector<T>>;
void solve() {
    vc<ll> board(36);
    ll ma = 0;
    rep(i, 6) rep(j, 6) cin >> board[i * 6 + j], ma = max(ma, board[i * 6 + j]);
    map<vc<ll>, ll> memo;
    queue<vc<ll>> que;
    que.push(board);
    memo[board] = 0;
    ll res = 11;
    vc<pair<ll, ll>> sz(ma);
    rep(i, ma) {
        ll h1 = -1, w1 = -1, h2 = -1, w2 = -1;
        rep(j, 6) {
            rep(k, 6) {
                if (board[j * 6 + k] == i + 1) {
                    h1 = j, w1 = k;
                    break;
                }
            }
            if (h1 != -1) break;
        }
        for (ll j = 5; j >= 0; j--) {
            for (ll k = 5; k >= 0; k--) {
                if (board[j * 6 + k] == i + 1) {
                    h2 = j, w2 = k;
                    break;
                }
            }
            if (h2 != -1) break;
        }
        sz[i] = {h2 - h1 + 1, w2 - w1 + 1};
    }
    if (sz[0].first == 2) {
        cout << -1 << endl;
        return;
    }
    ll dy[] = {1, 0, -1, 0}, dx[] = {0, 1, 0, -1};
    auto move = [&](vc<ll>& b, ll i, ll j, ll id, ll dis) -> void {
        rep(k, 4) {
            bool ok = true;
            rep(l, sz[id].first) rep(m, sz[id].second) {
                ll ny = i + l + dy[k], nx = j + m + dx[k];
                if (!(0 <= ny and ny < 6 and 0 <= nx and nx < 6)) ok = false;
                if (!(b[ny * 6 + nx] == id + 1 or b[ny * 6 + nx] == 0)) ok = false;
            }
            if (k % 2 == 0 and sz[id].first == 1) ok = false;
            if (k % 2 == 1 and sz[id].second == 1) ok = false;
            if (!ok) continue;
            auto c = b;
            rep(l, sz[id].first) rep(m, sz[id].second) c[(i + l) * 6 + j + m] = 0;
            rep(l, sz[id].first) rep(m, sz[id].second) {
                ll ny = i + l + dy[k], nx = j + m + dx[k];
                c[ny * 6 + nx] = id + 1;
            }
            if (memo.count(c)) continue;
            memo[c] = dis + 1;
            que.push(c);
        }
        if (id == 0) {
            if (i == 2) {
                if (j == 4) res = min(res, dis + 2);
            }
        }
    };
    while (!que.empty()) {
        auto from = que.front();
        que.pop();
        vc<ll> used(ma);
        ll dis = memo[from];
        rep(i, 6) rep(j, 6) {
            if (from[i * 6 + j]) {
                ll id = from[i * 6 + j] - 1;
                if (used[id]) continue;
                used[id] = true;
                move(from, i, j, id, dis);
            }
        }
    }
    cout << (res > 10 ? -1 : res) << endl;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed << setprecision(20);
    ll t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 4232kb

input:

2 2 0 0 0 7
3 0 0 5 0 7
3 1 1 5 0 7
3 0 0 5 0 0
4 0 0 0 8 8
4 0 6 6 6 0

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

0 2 0 6 6 0
0 2 0 0 7 0
0 3 1 1 7 0
0 3 4 4 8 0
0 5 5 5 8 0
0 0 0 0 0 0

output:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3940kb

input:

0 2 6 6 6 0
0 2 0 0 7 0
0 3 1 1 7 0
0 3 4 4 8 0
0 0 5 5 8 0
0 0 0 0 0 0

output:

8

result:

ok single line: '8'

Test #4:

score: 0
Accepted
time: 125ms
memory: 15120kb

input:

2 3 4 4 4 5
2 3 6 7 7 5
0 3 6 1 1 5
0 0 0 0 0 0
0 0 0 0 8 8
0 0 0 9 9 9

output:

8

result:

ok single line: '8'

Test #5:

score: 0
Accepted
time: 4ms
memory: 4048kb

input:

0 2 6 6 6 0
0 2 4 0 7 0
1 1 4 0 7 0
0 3 4 5 0 8
0 3 0 5 0 8
0 3 0 0 0 8

output:

10

result:

ok single line: '10'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3552kb

input:

0 2 6 6 6 7
0 2 4 0 0 7
1 1 4 0 0 7
0 3 4 5 0 8
0 3 0 5 0 8
0 3 0 0 0 8

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 3ms
memory: 4096kb

input:

0 2 3 4 4 4
0 2 3 5 5 5
1 1 0 0 0 0
0 6 7 7 0 10
0 6 8 8 8 10
0 6 0 9 9 10

output:

6

result:

ok single line: '6'

Test #8:

score: 0
Accepted
time: 6ms
memory: 4208kb

input:

0 2 2 2 4 4
5 5 3 3 0 0
1 1 0 6 0 0
0 0 0 6 0 10
0 0 0 7 9 10
0 8 8 7 9 10

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

5 4 4 3 3 3
5 0 0 0 0 2
5 0 0 1 1 2
6 0 0 0 0 9
6 0 0 0 0 9
7 7 8 8 8 0

output:

10

result:

ok single line: '10'

Test #10:

score: 0
Accepted
time: 330ms
memory: 29404kb

input:

0 0 5 5 5 0
2 0 6 6 0 0
2 1 1 0 8 0
0 0 0 0 8 7
0 3 3 0 0 7
0 0 0 4 4 0

output:

6

result:

ok single line: '6'

Test #11:

score: 0
Accepted
time: 12ms
memory: 4880kb

input:

0 0 0 0 2 2
0 0 0 0 3 4
1 1 0 0 3 4
0 0 0 0 3 0
0 0 0 0 5 5
0 0 0 6 6 6

output:

-1

result:

ok single line: '-1'

Test #12:

score: 0
Accepted
time: 30ms
memory: 7040kb

input:

2 2 2 0 0 3
0 0 4 0 0 3
1 1 4 0 0 3
0 5 0 0 6 6
7 5 0 0 8 8
7 5 0 0 0 0

output:

-1

result:

ok single line: '-1'