QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#509130#6314. 过河卒kymmykym100 ✓1244ms100236kbC++146.3kb2024-08-08 10:41:572024-08-08 10:41:57

Judging History

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

  • [2024-08-08 10:41:57]
  • 评测
  • 测评结果:100
  • 用时:1244ms
  • 内存:100236kb
  • [2024-08-08 10:41:57]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long 
int n,m;
typedef pair<int,int>pi;
pi dist[2][11][11][11][11][11][11];//{winner,dist}
int in[2][11][11][11][11][11][11];
int dx[]={-1,0,0,1};
int dy[]={0,-1,1,0};
char A[11][11];
int state(int turn, int ri1, int rj1, int ri2, int rj2, int bi1, int bj1){
	if(turn == 0){//R's turn
		if(bi1==1)return 1;
		if((ri1==bi1&&rj1==bj1) || (ri2==bi1 && rj2==bj1))return 1;//B wins
		bool can=0;
		for(int k=0;k<4;k++){
			int nx1=ri1+dx[k];
			int ny1=rj1+dy[k];
			if(nx1<1||nx1>n||ny1<1||ny1>m||A[nx1][ny1]=='#'||(nx1==ri2&&ny1==rj2))continue;
			can=1;
		}	
		for(int k=0;k<4;k++){
			int nx2=ri2+dx[k];
			int ny2=rj2+dy[k];
			if(nx2<1||nx2>n||ny2<1||ny2>m||A[nx2][ny2]=='#'||(nx2==ri1&&ny2==rj1))continue;
			can=1;
		}	
		if(!can)return 1; // black wins
		
		return 0;//tie
	} else{
		if(bi1==1)return 1;
		if((ri1==bi1&&rj1==bj1) || (ri2==bi1 && rj2==bj1))return -1; // R wins
		bool can=0;
		for(int k=0;k<3;k++){
			int nx1=bi1+dx[k];
			int ny1=bj1+dy[k];
			if(nx1<1||nx1>n||ny1<1||ny1>m||A[nx1][ny1]=='#')continue;
			can=1;
		}	
		if(!can)return -1;
		return 0;
	}
}
int id, T;
void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>A[i][j];
		}
	}
	queue<array<int,7>>qu;
	for(int turn=0;turn<=1;turn++){
		for(int ri1=1;ri1<=n;ri1++){
			for(int rj1=1;rj1<=m;rj1++){
				for(int ri2=1;ri2<=n;ri2++){
					for(int rj2=1;rj2<=m;rj2++){
						for(int bi1=1;bi1<=n;bi1++){
							for(int bj1=1;bj1<=m;bj1++){
								
								in[turn][ri1][rj1][ri2][rj2][bi1][bj1]=0;
								dist[turn][ri1][rj1][ri2][rj2][bi1][bj1]=make_pair(0,0);
					
								if(A[ri1][rj1] == '#' || A[ri2][rj2] == '#' || A[bi1][bj1] == '#')continue;
								if(ri1==ri2 && rj1==rj2)continue;
								int res=state(turn,ri1,rj1,ri2,rj2,bi1,bj1);
								
								if(res==-1){//red 
									
									dist[turn][ri1][rj1][ri2][rj2][bi1][bj1]=make_pair(-1,0);
									qu.push({turn,ri1,rj1,ri2,rj2,bi1,bj1});
								} else if(res==1){//black
									
									dist[turn][ri1][rj1][ri2][rj2][bi1][bj1]=make_pair(1,0);
									qu.push({turn,ri1,rj1,ri2,rj2,bi1,bj1});
								} else{
									if(turn == 0){
										for(int k=0;k<4;k++){
											int nx1=ri1+dx[k];
											int ny1=rj1+dy[k];
											if(nx1<1||nx1>n||ny1<1||ny1>m||A[nx1][ny1]=='#'||(nx1==ri2&&ny1==rj2))continue;
											in[turn][ri1][rj1][ri2][rj2][bi1][bj1]++;
										}	
										for(int k=0;k<4;k++){
											int nx2=ri2+dx[k];
											int ny2=rj2+dy[k];
											if(nx2<1||nx2>n||ny2<1||ny2>m||A[nx2][ny2]=='#'||(nx2==ri1&&ny2==rj1))continue;
											in[turn][ri1][rj1][ri2][rj2][bi1][bj1]++;
										}	
									} else{
										for(int k=0;k<3;k++){
											int nx1=bi1+dx[k];
											int ny1=bj1+dy[k];
											if(nx1<1||nx1>n||ny1<1||ny1>m||A[nx1][ny1]=='#')continue;
											in[turn][ri1][rj1][ri2][rj2][bi1][bj1]++;
										}	
									}
								}
							}
						}
					}
				}
			}
		}
	}
	
	while(qu.size()){
		array<int,7> cur=qu.front();qu.pop();
		int turn=cur[0], ri1=cur[1],rj1=cur[2],ri2=cur[3],rj2=cur[4],bi1=cur[5],bj1=cur[6];
		pi res=dist[turn][ri1][rj1][ri2][rj2][bi1][bj1];
		assert(res.first!=0);
		//cerr << turn << " " << ri1 <<" " << rj1 << " " << ri2 <<" "<<rj2<<" "<<bi1<<" " << bj1<<":"<<res.first<<"|"<<res.second<<endl;
		if(turn == 0){//it was r's turn, so before that it's black turn
			int nturn=1-turn;
			for(int k=1;k<4;k++){
				int px=bi1+dx[k];
				int py=bj1+dy[k];
				if(px<1||px>n||py<1||py>m||A[px][py]=='#'||dist[nturn][ri1][rj1][ri2][rj2][px][py].first != 0)continue;
				if(res.first == 1){//black wins here
					dist[nturn][ri1][rj1][ri2][rj2][px][py].first=res.first;
					dist[nturn][ri1][rj1][ri2][rj2][px][py].second=res.second+1;
					qu.push({nturn,ri1,rj1,ri2,rj2,px,py});
				} else{//red wins here. 
					in[nturn][ri1][rj1][ri2][rj2][px][py]--;
					if(in[nturn][ri1][rj1][ri2][rj2][px][py]==0){
						dist[nturn][ri1][rj1][ri2][rj2][px][py].first=res.first;
						dist[nturn][ri1][rj1][ri2][rj2][px][py].second=res.second+1;
						qu.push({nturn,ri1,rj1,ri2,rj2,px,py});
					}
				}
			}
		} else{//red turn before this. 
			int nturn=1-turn;
			for(int k=0;k<4;k++){
				int px=ri1+dx[k];
				int py=rj1+dy[k];
				if(px<1||px>n||py<1||py>m||A[px][py]=='#'||dist[nturn][px][py][ri2][rj2][bi1][bj1].first != 0)continue;
				if(res.first == -1){
					dist[nturn][px][py][ri2][rj2][bi1][bj1].first=res.first;
					dist[nturn][px][py][ri2][rj2][bi1][bj1].second=res.second+1;
					qu.push({nturn,px,py,ri2,rj2,bi1,bj1});
				} else{
					in[nturn][px][py][ri2][rj2][bi1][bj1]--;
					if(in[nturn][px][py][ri2][rj2][bi1][bj1]==0){
						dist[nturn][px][py][ri2][rj2][bi1][bj1].first=res.first;
						dist[nturn][px][py][ri2][rj2][bi1][bj1].second=res.second+1;
						qu.push({nturn,px,py,ri2,rj2,bi1,bj1});
					}
				}
			}
			for(int k=0;k<4;k++){
				int px=ri2+dx[k];
				int py=rj2+dy[k];
				if(px<1||px>n||py<1||py>m||A[px][py]=='#'||dist[nturn][ri1][rj1][px][py][bi1][bj1].first != 0)continue;
				if(res.first == -1){
					dist[nturn][ri1][rj1][px][py][bi1][bj1].first=res.first;
					dist[nturn][ri1][rj1][px][py][bi1][bj1].second=res.second+1;
					qu.push({nturn,ri1,rj1,px,py,bi1,bj1});
				} else{
					in[nturn][ri1][rj1][px][py][bi1][bj1]--;
					if(in[nturn][ri1][rj1][px][py][bi1][bj1]==0){
						dist[nturn][ri1][rj1][px][py][bi1][bj1].first=res.first;
						dist[nturn][ri1][rj1][px][py][bi1][bj1].second=res.second+1;
						qu.push({nturn,ri1,rj1,px,py,bi1,bj1});
					}
				}
			}
		}
	}
	vector<pi>red,black;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(A[i][j] == 'O'){
				red.push_back({i,j});
			} else if(A[i][j]=='X'){
				black.push_back({i,j});
			}
		}
	}
	pi res=dist[0][red[0].first][red[0].second][red[1].first][red[1].second][black[0].first][black[0].second];
	//cerr<<in[0][red[0].first][red[0].second][red[1].first][red[1].second][black[0].first][black[0].second];
	if(res.first == 0){
		cout<<"Tie\n";
	} else if(res.first == 1){
		cout<<"Black "<<res.second<<"\n";
	} else{
		cout<<"Red "<<res.second<<"\n";
	}
}
int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> id >> T;
	while(T--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 5
Accepted
time: 670ms
memory: 96572kb

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: 565ms
memory: 94600kb

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: 577ms
memory: 99652kb

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: 429ms
memory: 88948kb

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: 850ms
memory: 97736kb

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: 740ms
memory: 94908kb

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

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

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

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: 724ms
memory: 94584kb

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: 822ms
memory: 100236kb

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: 777ms
memory: 98752kb

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: 835ms
memory: 99244kb

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: 1244ms
memory: 97796kb

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: 564ms
memory: 89816kb

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: 596ms
memory: 92156kb

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: 849ms
memory: 95668kb

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: 629ms
memory: 95736kb

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: 668ms
memory: 94220kb

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: 651ms
memory: 90260kb

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