QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#183508 | #3128. Rush Hour Puzzle | ZHAOZHAO11 | AC ✓ | 2ms | 3664kb | C++17 | 3.7kb | 2023-09-19 16:24:55 | 2023-09-19 16:24:55 |
Judging History
answer
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int N;
unordered_map<ll, int> visited;
ll start_graph = 0;
typedef enum _Dir {
horizon = 0,
vertical,
} Dir;
class Vehicle {
public:
Dir dir;
vector<pii> locs;
void update_dir() {
if (locs.front().first - locs.back().first == 0)
this->dir = horizon;
else
this->dir = vertical;
}
pii get_forward_loc() {
int cr = locs.front().first;
int cc = locs.front().second;
int nr, nc;
if (dir == vertical) {
nr = cr - 1;
nc = cc;
}
else {
nr = cr;
nc = cc - 1;
}
return { nr, nc };
}
pii get_backward_loc() {
int cr = locs.back().first;
int cc = locs.back().second;
int nr, nc;
if (dir == vertical) {
nr = cr + 1;
nc = cc;
}
else {
nr = cr;
nc = cc + 1;
}
return { nr, nc };
}
bool forward_unmovable(int nr, int nc, ll graph, int step) {
if (nr < 0 || 6 <= nr || nc < 0 || 6 <= nc || graph & (1LL << (nr * 6 + nc)))
return true;
graph |= (1LL << (nr * 6 + nc));
graph ^= (1LL << (locs.back().first * 6 + locs.back().second));
if (visited.find(graph) != visited.end() && visited[graph] <= step)
return true;
return false;
}
bool back_unmovable(int nr, int nc, ll graph, int step) {
if (nr < 0 || 6 <= nr || nc < 0 || 6 <= nc || graph & (1LL << (nr * 6 + nc)))
return true;
graph |= (1LL << (nr * 6 + nc));
graph ^= (1LL << (locs.front().first * 6 + locs.front().second));
if (visited.find(graph) != visited.end() && visited[graph] <= step)
return true;
return false;
}
ll move_foward(ll graph) {
graph ^= (1LL << (locs.back().first * 6 + locs.back().second));
if (dir == vertical)
for (pii& loc : locs)
loc.first--;
else
for (pii& loc : locs)
loc.second--;
graph |= (1LL << (locs.front().first * 6 + locs.front().second));
return graph;
}
ll move_backward(ll graph) {
graph ^= (1LL << (locs.front().first * 6 + locs.front().second));
if (dir == vertical)
for (pii& loc : locs)
loc.first++;
else
for (pii& loc : locs)
loc.second++;
graph |= (1LL << (locs.back().first * 6 + locs.back().second));
return graph;
}
};
Vehicle vehicles[11];
void input() {
int val;
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
cin >> val;
if (val) {
vehicles[val].locs.push_back({ i, j });
start_graph |= (1LL << (i * 6 + j));
N = max(N, val);
}
}
}
for (int i = 1; i <= N; i++)
vehicles[i].update_dir();
visited.insert({ start_graph, 0 });
}
void DFS(int step, int& min_step, ll graph) {
if (vehicles[1].locs.back().second == 5) {
min_step = min(min_step, step);
return;
}
if (step == 8 || step >= min_step)
return;
for (int i = 1; i <= N; i++) {
Vehicle& curr = vehicles[i];
auto [nr, nc] = curr.get_forward_loc();
if (curr.forward_unmovable(nr, nc, graph, step) == false) {
ll new_graph = curr.move_foward(graph);
visited[new_graph] = step;
DFS(step + 1, min_step, new_graph);
curr.move_backward(graph);
}
auto [nnr, nnc] = curr.get_backward_loc();
if (curr.back_unmovable(nnr, nnc, graph, step) == false) {
ll new_graph = curr.move_backward(graph);
visited[new_graph] = step;
DFS(step + 1, min_step, new_graph);
curr.move_foward(graph);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("input.txt", "r", stdin);
input();
int min_step = 9;
DFS(0, min_step, start_graph);
if (min_step < 9)
cout << min_step + 2;
else
cout << -1;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
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: 3548kb
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: 3532kb
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: 1ms
memory: 3664kb
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: 1ms
memory: 3500kb
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: 3472kb
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: 1ms
memory: 3512kb
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: 1ms
memory: 3504kb
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: 1ms
memory: 3456kb
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: 2ms
memory: 3636kb
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: 1ms
memory: 3604kb
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: 0ms
memory: 3472kb
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'