QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#39684#2932. Checker Slide2873531385AC ✓77ms9960kbC++3.7kb2022-07-12 19:24:252022-07-12 19:24:27

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-12 19:24:27]
  • 评测
  • 测评结果：AC
  • 用时：77ms
  • 内存：9960kb
查看
  • [2022-07-12 19:24:25]
  • 提交

answer

#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>

int s[10], t[10];
struct Pos{
	bool g[6][6];
	long long val;
	Pos() {
		std::memset(g, 0, 36);
		val = 0;
	}
	void print() {
		for (int i = 0; i<6; ++i) {
			for (int j = 0; j<6; ++j) std::cout << g[i][j]<< " ";
			std::cout << "\n";
		}
	}
	void setval() {
		val = 0;
		for (int i = 0; i<6; ++i) {
			for (int j = 0; j<6; ++j) {
				val+=(g[i][j]*(1ll<<(6*i+j)));
			}
		}
	}
	bool operator<(const Pos& p) const {
		return val<p.val;
	}
	bool operator==(const Pos& p) const {
		return val==p.val;
	}
};
using pir = std::pair<int, Pos>;

std::vector<pir> pre;
Pos from, last;
std::set<long long> vis;
int cnt = 0;
int cnt_;
int bfs() {
	std::queue<std::pair<int, Pos>> Q;
	Q.push(pir(0, from));
	vis.insert(from.val);
	pre.push_back(pir(-1, from));
	while (!Q.empty()) {
		// if (++cnt_==100000) {
		// 	std::cout << "-------------\n";
		// 	exit(0);
		// }
		// std::cout << "++\n";
		auto [x, now] = Q.front();
		if (now==last) return x;
		Q.pop();
		Pos tmp;
		for (int i = 0; i<6; ++i) {
			for (int j = 0; j<6; ++j) {
				// std::cout << "+++\n";
				if (now.g[i][j]) {
					int ii = i;
					while (ii-1>=0 && !now.g[ii-1][j]) ii--;
					tmp = now;
					tmp.g[i][j] = 0;
					tmp.val-=(1ll<<(i*6+j));
					tmp.g[ii][j] = 1;
					tmp.val+=(1ll<<(ii*6+j));
					// tmp.setval();
					if (!vis.count(tmp.val)) {
						vis.insert(tmp.val);
						Q.push(pir(++cnt, tmp));
						pre.push_back(pir(x, tmp));
					}

					ii = i;
					while (ii+1<=5 && !now.g[ii+1][j]) ii++;
					tmp = now;
					tmp.g[i][j] = 0;
					tmp.val-=(1ll<<(i*6+j));
					tmp.g[ii][j] = 1;
					tmp.val+=(1ll<<(ii*6+j));
					// tmp.setval();
					if (!vis.count(tmp.val)) {
						vis.insert(tmp.val);
						Q.push(pir(++cnt, tmp));
						pre.push_back(pir(x, tmp));
					}
					int jj = j;
					while (jj-1>=0 && !now.g[i][jj-1]) jj--;
					tmp = now;
					tmp.g[i][j] = 0;
					tmp.val-=(1ll<<(i*6+j));
					tmp.g[i][jj] = 1;
					tmp.val+=(1ll<<(i*6+jj));
					// tmp.setval();
					if (!vis.count(tmp.val)) {
						vis.insert(tmp.val);
						Q.push(pir(++cnt, tmp));
						pre.push_back(pir(x, tmp));
					}
					jj = j;
					while (jj+1<=5 && !now.g[i][jj+1]) jj++;
					tmp = now;
					tmp.g[i][j] = 0;
					tmp.val-=(1ll<<(i*6+j));
					tmp.g[i][jj] = 1;
					tmp.val+=(1ll<<(i*6+jj));
					// tmp.setval();
					if (!vis.count(tmp.val)) {
						vis.insert(tmp.val);
						Q.push(pir(++cnt, tmp));
						pre.push_back(pir(x, tmp));
					}

				}

			}
		}
	}
	return -1;
}
struct Node {
	int a, b, c, d;
};
std::vector<Node> ans;
int main() {
	for (int i = 1; i<=8; ++i) std::cin >> s[i];
	for (int i = 1; i<=8; ++i) std::cin >> t[i];
	
	for (int i = 1; i<=4; ++i) {
		from.g[s[2*i-1]][s[2*i]] = 1;
		last.g[t[2*i-1]][t[2*i]] = 1;
	}
	from.setval(), last.setval();
	// std::cout << from.val << " " << last.val << "\n";
	int t = bfs();
	// std::cout << t << "\n";
	// std::cout << ans.size() << "==\n";
	// t = pre[t].first;
	Pos last_ = pre[t].second;
	// std::cout << last_.val << "+++\n";
	// last_.print();
	t = pre[t].first;
	for (; t!=-1; last_ = pre[t].second, t = pre[t].first) {
		int a, b, c, d;
		for (int i = 0; i<6; ++i) {
			for (int j = 0; j<6; ++j) {
				if (last_.g[i][j]^pre[t].second.g[i][j]) {
					if (last_.g[i][j]) {
						c = i, d = j;
					} else a = i, b = j;
				}
			}
		}
		ans.push_back({a, b, c, d});
	}
	std::cout << ans.size()<< "\n";
	reverse(ans.begin(), ans.end());
	for (auto&[a, b, c, d]:ans) {
		std::cout << a << " " << b <<" "<< c <<" "<< d << "\n";

	}


	return 0;
}

/*
5 5 5 0 0 5 0 0
2 2 2 1 1 2 1 1

*/
Source code, Language: C++

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 30ms
memory: 5796kb

input:

5 5 5 0 0 5 0 0
2 2 2 1 1 2 1 1

output:

12
0 5 4 5
5 0 1 0
0 0 0 5
4 5 1 5
5 5 2 5
1 5 1 1
0 5 1 5
1 5 1 2
1 1 5 1
1 0 1 1
5 1 2 1
2 5 2 2

result:

ok correct plan

Test #2:

score: 0
Accepted
time: 74ms
memory: 9944kb

input:

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

output:

18
1 0 5 0
2 1 2 5
5 0 5 5
5 5 3 5
2 5 0 5
0 5 0 4
0 3 5 3
3 5 3 3
3 2 0 2
0 2 0 3
0 3 2 3
3 3 4 3
5 3 5 0
5 0 0 0
0 0 0 3
0 3 1 3
2 3 3 3
3 3 3 5

result:

ok correct plan

Test #3:

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

input:

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

output:

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

result:

ok correct plan

Test #4:

score: 0
Accepted
time: 11ms
memory: 4192kb

input:

3 5 2 1 1 5 0 3
2 2 1 3 1 2 0 1

output:

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

result:

ok correct plan

Test #5:

score: 0
Accepted
time: 19ms
memory: 5084kb

input:

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

output:

8
0 3 0 2
0 2 1 2
1 2 1 4
1 5 0 5
0 5 0 2
0 2 1 2
1 2 1 3
1 3 0 3

result:

ok correct plan

Test #6:

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

input:

5 0 4 5 3 0 1 0
4 4 4 0 3 5 1 0

output:

6
5 0 4 0
4 0 4 4
4 5 5 5
5 5 5 0
5 0 4 0
3 0 3 5

result:

ok correct plan

Test #7:

score: 0
Accepted
time: 75ms
memory: 9184kb

input:

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

output:

18
1 2 1 0
4 3 4 5
4 5 5 5
5 3 5 4
5 4 2 4
1 4 1 1
1 0 5 0
5 5 5 1
5 1 2 1
1 1 1 5
1 5 5 5
5 0 5 4
5 4 3 4
2 4 2 2
2 1 5 1
5 5 5 2
5 1 0 1
5 2 3 2

result:

ok correct plan

Test #8:

score: 0
Accepted
time: 77ms
memory: 9408kb

input:

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

output:

20
1 0 5 0
1 3 5 3
1 5 5 5
5 3 5 4
5 4 2 4
5 0 5 4
5 4 3 4
2 4 2 0
1 4 2 4
2 4 2 1
2 0 5 0
5 5 5 1
5 0 0 0
0 0 0 5
0 5 5 5
5 5 5 2
5 1 3 1
2 1 2 5
2 5 5 5
5 5 5 3

result:

ok correct plan

Test #9:

score: 0
Accepted
time: 67ms
memory: 9664kb

input:

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

output:

16
2 3 0 3
0 3 0 5
3 1 0 1
3 3 0 3
0 3 0 4
0 5 5 5
3 4 1 4
0 4 0 2
5 5 5 0
0 2 5 2
5 0 5 1
5 1 1 1
0 1 0 0
0 0 5 0
5 0 5 1
5 2 0 2

result:

ok correct plan

Test #10:

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

input:

3 2 2 0 0 2 0 1
2 1 1 0 0 2 0 1

output:

5
0 2 2 2
2 0 2 1
2 2 0 2
3 2 1 2
1 2 1 0

result:

ok correct plan

Test #11:

score: 0
Accepted
time: 11ms
memory: 4620kb

input:

3 2 3 1 2 3 0 4
3 2 1 2 0 3 0 2

output:

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

result:

ok correct plan

Test #12:

score: 0
Accepted
time: 9ms
memory: 4204kb

input:

3 1 2 3 1 2 0 2
5 0 2 1 1 2 1 1

output:

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

result:

ok correct plan

Test #13:

score: 0
Accepted
time: 16ms
memory: 5884kb

input:

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

output:

7
0 4 0 0
3 1 3 0
3 0 1 0
1 0 1 5
2 3 2 0
0 0 1 0
3 3 0 3

result:

ok correct plan

Test #14:

score: 0
Accepted
time: 77ms
memory: 9960kb

input:

3 1 2 2 1 3 0 1
4 4 3 2 2 3 0 0

output:

18
0 1 2 1
1 3 1 0
2 2 2 5
2 1 2 4
3 1 3 0
1 0 2 0
2 0 2 3
2 4 5 4
2 5 2 4
2 4 4 4
5 4 5 0
5 0 4 0
4 0 4 3
4 3 3 3
3 0 3 2
3 3 5 3
5 3 5 0
5 0 0 0

result:

ok correct plan

Test #15:

score: 0
Accepted
time: 11ms
memory: 4664kb

input:

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

output:

7
2 5 5 5
3 1 0 1
5 3 5 4
5 4 3 4
5 5 0 5
0 5 0 2
2 4 0 4

result:

ok correct plan
English 繁體中文 简体中文

Server Time: 2025-02-01 18:00:05 | OpenSource Project