QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #39686 | #2932. Checker Slide | 2873531385 | AC ✓ | 106ms | 8312kb | C++ | 4.6kb | 2022-07-12 19:26:27 | 2022-07-12 19:26:28 |
Judging History
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
*/
Details
Tip: Click on the bar to expand more detailed information
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