QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#39686#2932. Checker Slide2873531385AC ✓106ms8312kbC++4.6kb2022-07-12 19:26:272022-07-12 19:26:28

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:26:28]
  • 评测
  • 测评结果：AC
  • 用时：106ms
  • 内存：8312kb
查看
  • [2022-07-12 19:26:27]
  • 提交

answer

#include<iostream>
#include<string.h>
#include<map>
#include<set>
#include<deque>

#define lint int64_t

using
namespace
	std;

class Config {

public:

	bool a[6][6];
	int x[4], y[4];

	Config() {

		memset(a, false, sizeof(a));
	}

	bool __equal(Config& B) {

		for (int i = 0; i < 6; i++) {

			for (int j = 0; j < 6; j++) {

				if (a[i][j]^B.a[i][j]) {

					return false;
				}
			}
		}

		return true;
	}

	void print() {

		for (int i = 0; i < 6; i++) {

			for (int j = 0; j < 6; j++) {

				putchar(a[i][j] ? '*' : '_');
			}
			putchar('\n');
		}
		putchar('\n');
	}

};

class Mpace {

public:

	int xs, ys, xt, yt;

	Mpace(int xs_ = 0, int ys_ = 0, int xt_ = 0, int yt_ = 0) {

		xs = xs_, ys = ys_, xt = xt_, yt = yt_;
	}
};

lint c2i(Config& c) {

	lint ans = 0;

	for (int i = 0; i < 6; i++) {

		for (int j = 0; j < 6; j++) {

			ans += c.a[i][j];
			ans <<= 1;
		}
	}

	return ans;
}

Config _move(Config now, int i, int dx, int dy) {

	if (dx == -1 && dy == 0) {

		int nxtx = 0;

		for (int k = 0; k < 4; k++) {

			if (now.x[k] < now.x[i] && now.y[k] == now.y[i]) {

				nxtx = max(nxtx, now.x[k] + 1);
			}
		}

		now.a[now.x[i]][now.y[i]] = false;
		now.a[nxtx][now.y[i]] = true;
		now.x[i] = nxtx;
	}
	else if (dx == 1 && dy == 0) {

		int nxtx = 5;

		for (int k = 0; k < 4; k++) {

			if (now.x[k] > now.x[i] && now.y[k] == now.y[i]) {

				nxtx = min(nxtx, now.x[k] - 1);
			}
		}

		now.a[now.x[i]][now.y[i]] = false;
		now.a[nxtx][now.y[i]] = true;
		now.x[i] = nxtx;
	}
	else if (dx == 0 && dy == -1) {

		int nxty = 0;

		for (int k = 0; k < 4; k++) {

			if (now.y[k] < now.y[i] && now.x[k] == now.x[i]) {

				nxty = max(nxty, now.y[k] + 1);
			}
		}

		now.a[now.x[i]][now.y[i]] = false;
		now.a[now.x[i]][nxty] = true;
		now.y[i] = nxty;
	}
	else if (dx == 0 && dy == 1) {

		int nxty = 5;

		for (int k = 0; k < 4; k++) {

			if (now.y[k] > now.y[i] && now.x[k] == now.x[i]) {

				nxty = min(nxty, now.y[k] - 1);
			}
		}

		now.a[now.x[i]][now.y[i]] = false;
		now.a[now.x[i]][nxty] = true;
		now.y[i] = nxty;
	}

	return now;
}

Config S, T;
deque<Mpace> kotae;
map<lint, lint> pre;
map<lint, Mpace> sousa;

void bfs() {

	deque<Config> q;

	q.push_back(S);

	pre[c2i(S)] = -1;

	while (!q.empty()) {

		Config now = q.front();

//		for(int i=0;i<6;i++){
//
//			for(int j=0;j<6;j++){
//
//				putchar(now.a[i][j]?'*':'_');
//			}
//			putchar('\n');
//		}
//		putchar('\n');

//		if(now.a[2][2]&&now.a[3][2]&&now.a[4][2]&&now.a[5][5]){
//
//			printf("^-^\n");
//
//			for(int i=0;i<4;i++){
//
//				cout<<now.x[i]<<' '<<now.y[i]<<endl;
//			}
//		}

		lint id = c2i(now);

		q.pop_front();

		if (now.__equal(T)) {

			break;
		}

		Config nxt;
		lint idnxt;

		for (int i = 0; i < 4; i++) {

			nxt = _move(now, i, -1, 0);

			idnxt = c2i(nxt);

			if (pre.find(idnxt) == pre.end()) {

				q.push_back(nxt);
				pre[idnxt] = id;
				sousa[idnxt] = Mpace(now.x[i], now.y[i], nxt.x[i], nxt.y[i]);
				if (nxt.__equal(T)) return;
			}

			nxt = _move(now, i, 1, 0);

			idnxt = c2i(nxt);

			if (pre.find(idnxt) == pre.end()) {

				q.push_back(nxt);
				pre[idnxt] = id;
				sousa[idnxt] = Mpace(now.x[i], now.y[i], nxt.x[i], nxt.y[i]);
				if (nxt.__equal(T)) return;
			}

			nxt = _move(now, i, 0, -1);

			idnxt = c2i(nxt);

			if (pre.find(idnxt) == pre.end()) {

				q.push_back(nxt);
				pre[idnxt] = id;
				sousa[idnxt] = Mpace(now.x[i], now.y[i], nxt.x[i], nxt.y[i]);
				if (nxt.__equal(T)) return;
			}

			nxt = _move(now, i, 0, 1);

			idnxt = c2i(nxt);

			if (pre.find(idnxt) == pre.end()) {

				q.push_back(nxt);
				pre[idnxt] = id;
				sousa[idnxt] = Mpace(now.x[i], now.y[i], nxt.x[i], nxt.y[i]);
				if (nxt.__equal(T)) return;
			}
		}
	}
}

signed main() {

	int u, v;

	for (int i = 0; i < 4; i++) {

		cin >> u >> v;
		S.a[u][v] = true;
		S.x[i] = u;
		S.y[i] = v;
	}

	for (int i = 0; i < 4; i++) {

		cin >> u >> v;
		T.a[u][v] = true;
		T.x[i] = u;
		T.y[i] = v;
	}

	bfs();

	lint iS = c2i(S);

	for (lint now = c2i(T); now != iS; now = pre[now]) {

		kotae.push_front(sousa[now]);
	}

	cout << kotae.size() << endl;

	for (Mpace& it : kotae) {

		cout << it.xs << ' ' << it.ys << ' ' << it.xt << ' ' << it.yt << endl;
	}

end:
	return EOF + 1;
}
/*
5 5 5 0 0 5 0 0
2 2 2 1 1 2 1 1

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

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

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

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

0 0 0 5 5 0 5 5
0 0 0 1 0 2 0 3
*/
源文件, 语言: C++

详细

Test #1:

score: 100
Accepted
time: 26ms
memory: 5496kb

input:

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

output:

12
5 0 1 0
0 5 4 5
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: 97ms
memory: 8068kb

input:

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

output:

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

result:

ok correct plan

Test #3:

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

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: 3ms
memory: 4032kb

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: 21ms
memory: 5284kb

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

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: 101ms
memory: 8056kb

input:

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

output:

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

result:

ok correct plan

Test #8:

score: 0
Accepted
time: 106ms
memory: 8312kb

input:

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

output:

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

result:

ok correct plan

Test #9:

score: 0
Accepted
time: 103ms
memory: 8052kb

input:

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

output:

16
3 4 0 4
3 3 5 3
5 3 5 5
3 1 0 1
2 3 5 3
5 5 5 4
5 4 1 4
0 4 0 2
5 3 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: 5ms
memory: 4048kb

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

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
2 3 0 3
0 2 2 2
0 1 0 2
2 2 1 2

result:

ok correct plan

Test #12:

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

input:

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

output:

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

result:

ok correct plan

Test #13:

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

input:

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

output:

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

result:

ok correct plan

Test #14:

score: 0
Accepted
time: 101ms
memory: 8088kb

input:

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

output:

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

result:

ok correct plan

Test #15:

score: 0
Accepted
time: 14ms
memory: 4872kb

input:

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

output:

7
3 1 0 1
2 5 5 5
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 繁體中文 简体中文

服务器时间: 2024-12-02 03:14:00 | 开源项目