QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#73227#2932. Checker Slideqdd#AC ✓373ms11176kbC++172.2kb2023-01-23 07:35:152023-01-23 07:35:17

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-23 07:35:17]
  • 评测
  • 测评结果:AC
  • 用时:373ms
  • 内存:11176kb
  • [2023-01-23 07:35:15]
  • 提交

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