QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#73227 | #2932. Checker Slide | qdd# | AC ✓ | 373ms | 11176kb | C++17 | 2.2kb | 2023-01-23 07:35:15 | 2023-01-23 07:35:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define move array<int,4>
#define grid array<array<int,6>, 6>
vector<move> find_valid_moves(grid &g){
vector<move> v;
for(int i=0; i<6; i++){
for(int j=0; j<6; j++){
if(g[i][j] == 0) continue;
int jump;
jump = i;
while(jump+1 < 6 && g[jump+1][j] == 0) jump++;
if(jump != i){
v.push_back({i,j,jump,j});
}
jump = i;
while(jump-1 >= 0 && g[jump-1][j] == 0) jump--;
if(jump != i){
v.push_back({i,j,jump,j});
}
jump = j;
while(jump+1 < 6 && g[i][jump+1] == 0) jump++;
if(jump != j){
v.push_back({i,j,i,jump});
}
jump = j;
while(jump-1 >= 0 && g[i][jump-1] == 0) jump--;
if(jump != j){
v.push_back({i,j,i,jump});
}
}
}
return v;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
grid start_grid, end_grid;
for(int i=0; i<6; i++){
for(int j=0; j<6; j++){
start_grid[i][j] = 0;
end_grid[i][j] = 0;
}
}
for(int i=0; i<4; i++){
int r, c;
cin >> r >> c;
start_grid[r][c] = 1;
}
for(int i=0; i<4; i++){
int r, c;
cin >> r >> c;
end_grid[r][c] = 1;
}
map<grid, move> mp;
queue<grid> q;
mp[start_grid] = {-1,-1,-1,-1};
q.push(start_grid);
while(!q.empty()){
grid cur = q.front(); q.pop();
if(cur == end_grid) break;
vector<move> v = find_valid_moves(cur);
for(move &m : v){
assert(cur[m[0]][m[1]] == 1);
assert(cur[m[2]][m[3]] == 0);
cur[m[0]][m[1]] = 0;
cur[m[2]][m[3]] = 1;
if(!mp.count(cur)){
// cout << "Move " << m[0] << ',' << m[1] << " to " << m[2] << ',' << m[3] << endl;
mp[cur] = m;
q.push(cur);
}
cur[m[0]][m[1]] = 1;
cur[m[2]][m[3]] = 0;
}
// break;
}
vector<move> ans;
grid cur = end_grid;
while(cur != start_grid){
assert(mp.count(cur));
ans.push_back(mp[cur]);
auto [er, ec, sr, sc] = mp[cur];
assert(cur[sr][sc] == 1);
assert(cur[er][ec] == 0);
cur[sr][sc] = 0;
cur[er][ec] = 1;
}
reverse(ans.begin(), ans.end());
cout << ans.size() << endl;
for(auto &[sr,sc,er,ec] : ans){
cout << sr << ' ' << sc << ' ' << er << ' ' << ec << endl;
}
}
详细
Test #1:
score: 100
Accepted
time: 126ms
memory: 7196kb
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: 350ms
memory: 10704kb
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: 11ms
memory: 4216kb
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: 36ms
memory: 5420kb
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: 102ms
memory: 7156kb
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: 16ms
memory: 4508kb
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: 373ms
memory: 10872kb
input:
5 3 4 3 1 4 1 2 3 4 3 2 2 2 0 1
output:
18 1 2 1 3 1 3 3 3 1 4 0 4 4 3 4 0 5 3 4 3 4 3 4 1 4 0 0 0 0 4 0 1 0 1 3 1 0 0 0 5 4 1 4 5 0 5 3 5 3 5 3 4 3 3 3 2 3 1 0 1 4 5 0 5 0 5 0 2 0 2 2 2
result:
ok correct plan
Test #8:
score: 0
Accepted
time: 373ms
memory: 11176kb
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: 362ms
memory: 10720kb
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: 12ms
memory: 4564kb
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: 61ms
memory: 6236kb
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: 41ms
memory: 5668kb
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: 105ms
memory: 7488kb
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: 351ms
memory: 10744kb
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 5 3 1 3 5 1 5 2 5 2 2 2 4 2 1 2 3 2 4 5 4 2 5 2 4 2 4 4 4 3 5 3 0 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: 68ms
memory: 6304kb
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