QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#509147#6314. 过河卒TheRaptor#100 ✓818ms54944kbC++146.6kb2024-08-08 11:10:562024-08-08 11:10:56

Judging History

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

  • [2024-08-08 11:10:56]
  • 评测
  • 测评结果:100
  • 用时:818ms
  • 内存:54944kb
  • [2024-08-08 11:10:56]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int pot[2][11][11][11][11][11][11];
pair<int,int> ans[2][11][11][11][11][11][11];
pair<int,int> db[]={{-1,0},{0,1},{0,-1}},dr[]={{-1,0},{1,0},{0,1},{0,-1}};
queue<tuple<pair<int,int>,int,pair<int,int>,pair<int,int>,pair<int,int> > > q;
//0 is red, 1 is black
// win, num turn, who turn, 2x red pos, black pos
int n,m;
int arr[11][11];
bool valid(int x, int y){
	if(x<0||x>=n||y<0||y>=m) return false;
	if(arr[x][y]==1) return false;
	return true;
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int st,t;
	cin >> st >> t;
	while(t--){
		cin >> n >> m;
		pair<int,int> str[3];
		bool got=false;
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				char c;
				cin >> c;
				arr[i][j]=0;
				if(c=='.') continue;
				if(c=='#') arr[i][j]=1;
				else if(c=='X') str[2]={i,j};
				else if(!got) str[0]={i,j},got=true;
				else str[1]={i,j};
			}
		}
		while(!q.empty()) q.pop();
		for(int a1=0; a1<n; a1++) for(int a2=0; a2<m; a2++) for(int a3=0; a3<n; a3++){
			for(int a4=0; a4<m; a4++) for(int a5=0; a5<n; a5++) for(int a6=0; a6<m; a6++){
				pot[0][a1][a2][a3][a4][a5][a6]=0;
				ans[0][a1][a2][a3][a4][a5][a6]={0,0};
				if(!(valid(a1,a2)&&valid(a3,a4)&&valid(a5,a6))) continue;
				if(a1==a3&&a2==a4) continue;
				for(auto [i,j]:dr){
					int nx=a1+i,ny=a2+j;
					if(!valid(nx,ny)) continue;
					if(nx==a3&&ny==a4) continue;
					pot[0][a1][a2][a3][a4][a5][a6]++;
				}
				for(auto [i,j]:dr){
					int nx=a3+i,ny=a4+j;
					if(!valid(nx,ny)) continue;
					if(nx==a1&&ny==a2) continue;
					pot[0][a1][a2][a3][a4][a5][a6]++;
				}
				if(pot[0][a1][a2][a3][a4][a5][a6]==0){
					q.push({{1,0},0,{a1,a2},{a3,a4},{a5,a6}});
				}
				pot[1][a1][a2][a3][a4][a5][a6]=0;
				for(auto [i,j]:db){
					int nx=a5+i,ny=a6+j;
					if(!valid(nx,ny)) continue;
					pot[1][a1][a2][a3][a4][a5][a6]++;
				}
				
				if(pot[1][a1][a2][a3][a4][a5][a6]==0){
					q.push({{0,0},1,{a1,a2},{a3,a4},{a5,a6}});
				}
			}
		}
		if(pot[0][str[0].first][str[0].second][str[1].first][str[1].second][str[2].first][str[2].second]==0){
			cout << "Black 0\n";
			continue;
		}
		if(pot[1][str[0].first][str[0].second][str[1].first][str[1].second][str[2].first][str[2].second]==0){
			cout << "Red 1\n";
			continue;
		}
		
		for(int a1=0; a1<n; a1++) for(int a2=0; a2<m; a2++) for(int a3=0; a3<n; a3++){
			for(int a4=0; a4<m; a4++) for(int a6=0; a6<m; a6++){
				if(!(valid(a1,a2)&&valid(a3,a4)&&valid(0,a6))) continue;
				q.push({{1,0},0,{a1,a2},{a3,a4},{0,a6}});
				ans[0][a1][a2][a3][a4][0][a6]={1,0};
				pot[0][a1][a2][a3][a4][0][a6]=0;
			}
		}
		for(int a1=0; a1<n; a1++) for(int a2=0; a2<m; a2++) for(int a3=0; a3<n; a3++){
			for(int a4=0; a4<m; a4++){
				if(!(valid(a1,a2)&&valid(a3,a4))) continue;
				q.push({{1,0},0,{a1,a2},{a3,a4},{a1,a2}});
				ans[0][a1][a2][a3][a4][a1][a2]={1,0};
				pot[0][a1][a2][a3][a4][a1][a2]=0;
				q.push({{1,0},0,{a1,a2},{a3,a4},{a3,a4}});
				ans[0][a1][a2][a3][a4][a3][a4]={1,0};
				pot[0][a1][a2][a3][a4][a3][a4]=0;
				
				q.push({{0,0},1,{a1,a2},{a3,a4},{a1,a2}});
				ans[1][a1][a2][a3][a4][a1][a2]={0,0};
				pot[1][a1][a2][a3][a4][a1][a2]=0;
				q.push({{0,0},1,{a1,a2},{a3,a4},{a3,a4}});
				ans[1][a1][a2][a3][a4][a3][a4]={0,0};
				pot[1][a1][a2][a3][a4][a3][a4]=0;
			}
		}
		while(!q.empty()){
			int who;
			pair<int,int> win,r1,r2,b1;
			tie(win,who,r1,r2,b1) = q.front();
			q.pop();
			who^=1;
			win.second++;
			if(win.first==who){
				if(who==0){ //red
					for(auto [i,j]:dr){
						int nx=r1.first+i,ny=r1.second+j;
						if(!valid(nx,ny)) continue;
						if(nx==r2.first&&ny==r2.second) continue;
						if(pot[who][nx][ny][r2.first][r2.second][b1.first][b1.second]!=0){
							pot[who][nx][ny][r2.first][r2.second][b1.first][b1.second]=0;
							ans[who][nx][ny][r2.first][r2.second][b1.first][b1.second]=win;
							q.push({win,who,{nx,ny},r2,b1});
						}
					}
					for(auto [i,j]:dr){
						int nx=r2.first+i,ny=r2.second+j;
						if(!valid(nx,ny)) continue;
						if(nx==r1.first&&ny==r1.second) continue;
						if(pot[who][r1.first][r1.second][nx][ny][b1.first][b1.second]!=0){
							pot[who][r1.first][r1.second][nx][ny][b1.first][b1.second]=0;
							ans[who][r1.first][r1.second][nx][ny][b1.first][b1.second]=win;
							q.push({win,who,r1,{nx,ny},b1});
						}
					}
				}
				else{
					for(auto [i,j]:db){
						int nx=b1.first-i,ny=b1.second-j;
						if(!valid(nx,ny)) continue;
						if(pot[who][r1.first][r1.second][r2.first][r2.second][nx][ny]!=0){
							pot[who][r1.first][r1.second][r2.first][r2.second][nx][ny]=0;
							ans[who][r1.first][r1.second][r2.first][r2.second][nx][ny]=win;
							q.push({win,who,r1,r2,{nx,ny}});
						}
					}
				}
			}
			else{ //bad
				if(who==0){ //red
					for(auto [i,j]:dr){
						int nx=r1.first+i,ny=r1.second+j;
						if(!valid(nx,ny)) continue;
						if(nx==r2.first&&ny==r2.second) continue;
						if(pot[who][nx][ny][r2.first][r2.second][b1.first][b1.second]!=0){
							pot[who][nx][ny][r2.first][r2.second][b1.first][b1.second]--;
							if(pot[who][nx][ny][r2.first][r2.second][b1.first][b1.second]==0){
								ans[who][nx][ny][r2.first][r2.second][b1.first][b1.second]=win;
								q.push({win,who,{nx,ny},r2,b1});
							}
						}
					}
					for(auto [i,j]:dr){
						int nx=r2.first+i,ny=r2.second+j;
						if(!valid(nx,ny)) continue;
						if(nx==r1.first&&ny==r1.second) continue;
						if(pot[who][r1.first][r1.second][nx][ny][b1.first][b1.second]!=0){
							pot[who][r1.first][r1.second][nx][ny][b1.first][b1.second]--;
							if(pot[who][r1.first][r1.second][nx][ny][b1.first][b1.second]==0){
								ans[who][r1.first][r1.second][nx][ny][b1.first][b1.second]=win;
								q.push({win,who,r1,{nx,ny},b1});
							}
						}
					}
				}
				else{
					for(auto [i,j]:db){
						int nx=b1.first-i,ny=b1.second-j;
						if(!valid(nx,ny)) continue;
						if(pot[who][r1.first][r1.second][r2.first][r2.second][nx][ny]!=0){
							pot[who][r1.first][r1.second][r2.first][r2.second][nx][ny]--;
							if(pot[who][r1.first][r1.second][r2.first][r2.second][nx][ny]==0){
								ans[who][r1.first][r1.second][r2.first][r2.second][nx][ny]=win;
								q.push({win,who,r1,r2,{nx,ny}});
							}
						}
					}
				}
			}
		}
		if(pot[0][str[0].first][str[0].second][str[1].first][str[1].second][str[2].first][str[2].second]){
			cout << "Tie\n";
			continue;
		}
		pair<int,int> ret=ans[0][str[0].first][str[0].second][str[1].first][str[1].second][str[2].first][str[2].second];
		if(ret.first==0) cout << "Red ", assert(ret.second&1);
		else cout << "Black ", assert(ret.second%2==0);
		cout << ret.second << '\n';
	}
}

詳細信息


Pretests


Final Tests

Test #1:

score: 5
Accepted
time: 349ms
memory: 52820kb

input:

1 10
10 10
.#......#.
..#....#..
#..#..#..#
..#.O..#..
.#......#.
...####...
##..X...##
..........
.##.O####.
..........
10 10
.##..##...
.....##...
..X#.#....
#........#
..#.#.#...
.#...#.#..
#..#.#.#..
..#..#.#.#
...##O#...
..##O#.#..
4 1
O
O
#
X
10 10
.##.....##
...#....##
.#.#...#..
.O###.....
#...

output:

Tie
Black 0
Black 0
Tie
Black 0
Tie
Black 0
Black 0
Tie
Tie

result:

ok 10 lines

Test #2:

score: 5
Accepted
time: 323ms
memory: 52228kb

input:

2 10
10 10
.#.####..#
.##..#####
##.###X###
#....####.
.#.#######
#.#O###.##
..##.####.
..########
##########
##O#.#.###
10 10
..#.###.##
......#..#
....#O....
#..#.....#
...#.#####
.....#..#.
..#.....#O
X#....###.
#.....##..
.#..##....
10 10
.......##.
.O##...##.
..#.......
####..O...
....#...##
.....

output:

Black 0
Tie
Tie
Black 0
Black 0
Tie
Black 0
Tie
Tie
Black 0

result:

ok 10 lines

Test #3:

score: 5
Accepted
time: 262ms
memory: 48968kb

input:

3 10
10 10
##.#######
###..###OO
##X####.##
...#######
#..###...#
##...#####
##..#.####
..##..##.#
###..#.#.#
#.###..##.
10 10
.##..##...
.....##...
..X#.#....
#........#
..#.#.#...
.#...#.#..
#..#.#.#..
..#..#.#.#
...##O#...
..##O#.#..
10 10
..........
.X........
..........
..........
..#.......
.....

output:

Black 0
Black 0
Black 0
Black 0
Black 0
Tie
Tie
Tie
Tie
Tie

result:

ok 10 lines

Test #4:

score: 5
Accepted
time: 250ms
memory: 48176kb

input:

4 10
10 10
.#......#.
..#....#..
#..#..#..#
..#.O..#..
.#......#.
...####...
##..X...##
..........
.##.O####.
..........
10 10
...#.##...
..####.##.
###.######
.####O#.X#
...####..#
.##O#..#.#
##.#..###.
#.#.#....#
.#.#####.#
.##.#.#.##
3 2
OO
##
#X
10 10
.##.##...#
..##..#.#O
.#O#.#...#
#.#.#..##.
...

output:

Tie
Black 0
Black 0
Black 0
Black 0
Black 0
Tie
Tie
Tie
Tie

result:

ok 10 lines

Test #5:

score: 5
Accepted
time: 541ms
memory: 52228kb

input:

5 10
10 10
..........
....O.....
..........
...X......
..........
..........
..........
..........
##########
.......O..
10 10
..........
..O.......
..........
..........
..........
X.........
..........
..........
##########
.......O..
10 1
.
.
.
O
.
.
.
X
#
O
10 1
O
.
.
.
.
.
.
X
#
O
10 10
..........

output:

Red 9
Red 21
Black 12
Red 7
Black 8
Red 23
Black 14
Red 25
Red 23
Red 1

result:

ok 10 lines

Test #6:

score: 5
Accepted
time: 468ms
memory: 53216kb

input:

6 10
10 10
.....O....
..........
..........
..........
..........
.X........
..........
..........
##########
...O......
10 1
O
.
.
.
.
.
.
X
#
O
10 10
..........
..O.......
..........
..........
..........
X.........
..........
..........
##########
.......O..
10 10
..........
.....O....
.............

output:

Red 17
Red 7
Red 21
Red 17
Black 2
Black 12
Black 6
Red 25
Red 23
Black 10

result:

ok 10 lines

Test #7:

score: 5
Accepted
time: 0ms
memory: 40504kb

input:

7 10
10 1
.
O
#
.
.
X
.
#
.
O
10 1
O
.
.
.
.
.
.
X
.
O
10 1
.
.
#
O
O
#
#
.
.
X
5 1
O
O
.
X
.
10 1
O
#
.
.
.
.
.
X
.
O
9 1
O
#
O
.
.
.
.
.
X
10 1
.
.
.
.
X
O
.
#
.
O
10 1
O
O
.
#
.
.
.
.
.
X
10 1
.
.
.
.
.
.
X
.
O
O
10 1
O
.
.
.
#
X
#
O
.
.

output:

Red 5
Red 7
Black 0
Black 2
Red 11
Black 10
Red 1
Red 11
Black 12
Red 1

result:

ok 10 lines

Test #8:

score: 5
Accepted
time: 0ms
memory: 40600kb

input:

8 10
10 1
.
.
#
.
X
#
.
O
#
O
10 1
.
O
O
.
X
.
.
.
.
.
10 1
O
O
.
.
.
.
.
.
.
X
5 1
.
#
O
X
O
10 1
O
#
.
.
.
.
X
.
.
O
9 1
O
#
O
.
.
.
.
X
.
10 1
#
.
.
.
X
O
.
#
.
O
10 1
O
O
#
#
.
.
.
.
.
X
10 1
#
.
.
.
.
.
X
.
O
O
10 1
.
#
O
.
#
O
.
X
#
.

output:

Red 3
Red 3
Red 9
Red 1
Red 9
Red 5
Red 1
Black 0
Red 11
Red 3

result:

ok 10 lines

Test #9:

score: 5
Accepted
time: 0ms
memory: 42620kb

input:

9 10
10 1
#
O
#
.
.
X
.
#
.
O
10 1
O
.
.
.
X
.
.
.
.
O
10 1
.
.
#
O
O
.
#
.
.
X
5 1
O
O
.
X
.
10 1
O
#
.
#
.
.
.
X
.
O
9 1
O
.
#
O
.
.
.
X
.
10 1
.
.
.
.
X
O
.
.
.
O
10 1
O
O
.
#
#
.
.
.
.
X
10 1
.
.
.
.
X
.
#
.
O
O
10 1
.
#
O
#
O
.
.
X
#
.

output:

Red 5
Red 5
Red 5
Black 2
Red 7
Red 5
Red 1
Red 9
Black 8
Red 3

result:

ok 10 lines

Test #10:

score: 5
Accepted
time: 493ms
memory: 53264kb

input:

10 10
10 10
.###..###.
.....O...#
.##.#.....
..##.##.X#
##......#.
#...#.....
....##...#
..#..O##.#
#..#.##...
.....##.#.
10 10
#...##..#.
#......##.
..##....#.
#.#.##..#O
.O...#.##.
.....##.X.
.###......
....#.#.#.
.......##.
###...##.#
10 10
#.#.......
..##..##..
..##.#X..O
....#.....
#..#....#.
#...

output:

Red 7
Red 5
Red 3
Black 2
Red 9
Tie
Tie
Red 9
Red 9
Red 7

result:

ok 10 lines

Test #11:

score: 5
Accepted
time: 535ms
memory: 54476kb

input:

11 10
10 10
...#.....#
..#.......
##.##.###.
##...#.##X
.....#...#
...#.#.O.#
..#...#...
.....#....
......#..#
#...#...O#
10 10
..###O#O#.
.#.###.##.
##..#..#..
....#X....
........##
........##
#...##....
...#..###.
........#.
..#...#.#.
10 10
######...#
O.X.O####.
#.#.#.#...
#.......#.
...##...#.
....

output:

Black 8
Black 0
Black 2
Tie
Tie
Red 9
Tie
Red 9
Red 9
Red 1

result:

ok 10 lines

Test #12:

score: 5
Accepted
time: 526ms
memory: 54464kb

input:

12 10
10 10
##..##..O.
.#........
.#.......#
..........
#.........
.XO##.....
#.........
..........
..........
..........
5 6
#.####
#.####
#.OO##
#X####
######
10 10
....######
.#########
O...##.###
.#########
....######
####....#.
####.####.
####.O..#.
#######.#.
####....#X
10 10
..........
.........

output:

Red 1
Black 2
Red 9
Tie
Red 9
Black 6
Tie
Tie
Red 3
Tie

result:

ok 10 lines

Test #13:

score: 5
Accepted
time: 546ms
memory: 54092kb

input:

13 10
10 10
.##...#...
.#####..##
#..#..#..#
#........#
#...#.#.#.
....#.....
..#####...
....#..#..
..##O#....
.X...O##.#
10 10
.##......#
..#..##..O
...#.##...
##..#O..##
..#...#...
###.....#X
..#.......
.##.#.#...
.#.#.#..#.
#......#.#
10 10
.........#
..........
O.........
..........
....O.....
....

output:

Black 6
Red 9
Red 9
Red 9
Black 8
Tie
Red 7
Red 7
Tie
Tie

result:

ok 10 lines

Test #14:

score: 5
Accepted
time: 818ms
memory: 54944kb

input:

14 10
10 10
.......O..
..........
..........
O.........
..........
..........
..........
..........
.......X..
..........
10 10
.##...#...
.#####..##
...#..##.#
#........#
#...#.#.#.
....#.....
..#####...
....#..#..
..##O#....
.X...O##.#
10 10
.#..O...#.
...####...
##.X....##
..........
.#.O..#...
....

output:

Red 27
Black 6
Tie
Black 8
Red 17
Red 63
Black 12
Red 17
Black 16
Red 5

result:

ok 10 lines

Test #15:

score: 5
Accepted
time: 409ms
memory: 48880kb

input:

15 10
10 10
.########O
.........#
########.#
.........#
.#########
..........
#########.
..........
.#########
.......O.X
10 10
.##...#...
.#####..##
...#..##.#
#........#
#...#.#.#.
....#.....
..#####...
....#..#..
..##O#....
.X...O##.#
10 8
####....
...#..#.
.###..#.
...#.O#.
##.#..#.
...####.
.##...

output:

Black 102
Black 6
Red 13
Red 9
Tie
Red 63
Red 93
Red 139
Red 45
Black 44

result:

ok 10 lines

Test #16:

score: 5
Accepted
time: 413ms
memory: 50140kb

input:

16 10
10 10
....######
.#########
O...##.###
.#########
....######
####....#.
####.####.
####.O..#.
#######.#.
####....#X
10 10
.#..O...#.
...####...
##.X....##
..........
.#.O..#...
.#....#...
.#....#...
..####....
..........
..........
10 10
O#########
#..#..#...
..#..#..##
.#..#..#..
...#..#..#
....

output:

Red 9
Tie
Black 50
Red 333
Red 41
Black 6
Red 133
Black 24
Red 111
Red 101

result:

ok 10 lines

Test #17:

score: 5
Accepted
time: 575ms
memory: 52748kb

input:

17 10
10 10
##########
..........
..........
..########
..........
#########.
.O........
..........
#.........
O#X.......
10 10
.##...#...
.#####..##
...#..##.#
#........#
#...#.#.#.
....#.....
..#####...
....#..#..
..##O#....
.X...O##.#
10 10
#.......O.
..#.......
...##.##..
..........
..........
....

output:

Black 60
Black 6
Red 53
Red 35
Tie
Tie
Red 9
Red 65
Tie
Red 63

result:

ok 10 lines

Test #18:

score: 5
Accepted
time: 422ms
memory: 53424kb

input:

18 10
10 10
O.........
#..#..###.
.#.##...#.
..X.......
.####.....
.##...##.#
...#..###.
...###..O#
..#..#....
.......###
10 10
...#.....O
........#.
........X.
..........
...#......
..........
.........#
.....O....
..#.......
..........
10 10
..O.#.....
#.#...#...
...#..###.
....#.....
..#..#..#.
#...

output:

Red 159
Tie
Red 73
Black 36
Black 56
Black 6
Red 15
Black 0
Red 63
Black 2

result:

ok 10 lines

Test #19:

score: 5
Accepted
time: 437ms
memory: 52920kb

input:

19 10
10 10
.....#....
...#.#.#.#
#..#.##.#.
.##.....#.
.#..##.#.#
...#......
#.#.#.##..
##...#O##.
..#.#O....
.#...#..X.
10 10
.O....#...
.####....#
.###...#..
..........
###....##.
....#..##.
.#.#.#....
.##.O#..#.
#..#...#..
...#....X#
10 10
O#########
#..#..#...
..#..#..##
.#..#..#..
...#..#..#
....

output:

Black 6
Red 57
Black 50
Red 11
Tie
Red 129
Red 99
Black 0
Red 111
Red 27

result:

ok 10 lines

Test #20:

score: 5
Accepted
time: 429ms
memory: 48592kb

input:

20 10
10 10
.##.....##
...#....##
.#.#...#..
.O###.....
###.......
......###.
.....#..O.
##........
..#...X...
.##.......
10 10
#...#.##..
.O##.....#
#.#.....#.
.#...#....
....#..#..
.###......
....O##.#.
.#.#.....#
..........
.#.#...X#.
10 10
......###.
..#.#..##.
.#.......#
.#.#..###.
..#.#..#..
#...

output:

Tie
Red 63
Red 61
Red 9
Black 6
Black 0
Tie
Red 333
Red 57
Tie

result:

ok 10 lines

Extra Test:

score: 0
Extra Test Passed