QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#743410#3128. Rush Hour Puzzlevwxyz#AC ✓467ms9896kbC++232.7kb2024-11-13 19:09:172024-11-13 19:09:17

Judging History

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

  • [2024-11-13 19:09:17]
  • 评测
  • 测评结果:AC
  • 用时:467ms
  • 内存:9896kb
  • [2024-11-13 19:09:17]
  • 提交

answer

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

const int N = 6;
int M;

using Grid = array<array<int, N>, N>;
unordered_map<string, int> memo;

string grid_to_string(const Grid& A) {
    stringstream ss;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            ss << A[i][j] << ",";
        }
    }
    return ss.str();
}

vector<Grid> move(const Grid& A, int a) {
    vector<int> I, J;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (A[i][j] == a) {
                I.push_back(i);
                J.push_back(j);
            }
        }
    }

    vector<Grid> retu;
    if (J.front() == J.back()) {
        for (int di : {-1, 1}) {
            Grid B = A;
            bool ok = true;
            for (size_t idx = 0; idx < I.size(); ++idx) {
                B[I[idx]][J[idx]] = 0;
            }
            for (size_t idx = 0; idx < I.size(); ++idx) {
                int ni = I[idx] + di, nj = J[idx];
                if (0 <= ni && ni < N && 0 <= nj && nj < N && (B[ni][nj] == 0 || B[ni][nj] == a)) {
                    B[ni][nj] = A[I[idx]][J[idx]];
                } else {
                    ok = false;
                    break;
                }
            }
            if (ok) retu.push_back(B);
        }
    } else {
        for (int dj : {-1, 1}) {
            Grid B = A;
            bool ok = true;
            for (size_t idx = 0; idx < I.size(); ++idx) {
                B[I[idx]][J[idx]] = 0;
            }
            for (size_t idx = 0; idx < I.size(); ++idx) {
                int ni = I[idx], nj = J[idx] + dj;
                if (0 <= ni && ni < N && 0 <= nj && nj < N && (B[ni][nj] == 0 || B[ni][nj] == a)) {
                    B[ni][nj] = A[I[idx]][J[idx]];
                } else {
                    ok = false;
                    break;
                }
            }
            if (ok) retu.push_back(B);
        }
    }

    return retu;
}

int solve(Grid A, int cnt) {
    if (cnt <= 1) return -1;
    if (A[2][5] == 1 && A[2][4] == 1) return cnt - 2;

    string key = grid_to_string(A) + "," + to_string(cnt);
    if (memo.count(key)) return memo[key];

    int retu = -1;
    for (int a = 1; a <= M; ++a) {
        for (auto& B : move(A, a)) {
            retu = max(retu, solve(B, cnt - 1));
        }
    }

    return memo[key] = retu;
}

int main() {
    Grid A;
    M = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> A[i][j];
            M = max(M, A[i][j]);
        }
    }

    int ans = solve(A, 10);
    if (ans != -1) ans = 10 - ans;
    cout << ans << endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 11ms
memory: 3728kb

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: 2ms
memory: 3624kb

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: 4ms
memory: 3704kb

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: 55ms
memory: 4812kb

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: 10ms
memory: 3712kb

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: 3636kb

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: 4ms
memory: 3628kb

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: 16ms
memory: 3884kb

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: 3632kb

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: 467ms
memory: 9896kb

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: 16ms
memory: 3920kb

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: 10ms
memory: 3804kb

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'