QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#743410 | #3128. Rush Hour Puzzle | vwxyz# | AC ✓ | 467ms | 9896kb | C++23 | 2.7kb | 2024-11-13 19:09:17 | 2024-11-13 19:09:17 |
Judging History
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'