QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#183508#3128. Rush Hour PuzzleZHAOZHAO11AC ✓2ms3664kbC++173.7kb2023-09-19 16:24:552023-09-19 16:24:55

Judging History

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

  • [2023-09-19 16:24:55]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:3664kb
  • [2023-09-19 16:24:55]
  • 提交

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'