QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#243053#7334. EndgamePetroTarnavskyi#AC ✓157ms59040kbC++204.0kb2023-11-07 20:19:292023-11-07 20:19:29

Judging History

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

  • [2023-11-07 20:19:29]
  • 评测
  • 测评结果:AC
  • 用时:157ms
  • 内存:59040kb
  • [2023-11-07 20:19:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); i--)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int INF = 1e9;
const int N = 1 << 18;

bool ok(int x)
{
	return 0 <= x && x < 8;
}

struct State
{
	int r1, c1, r2, c2, r3, c3;
	bool isValid() const
	{
		return ok(r1) && ok(c1) && ok(r2) && ok(c2) && ok(r3) && ok(c3)
			&& (abs(r3 - r1) > 1 || abs(c3 - c1) > 1)
			&& (r2 != r1 || c2 != c1);
	}
	bool isRookCaptured() const
	{
		return r2 == r3 && c2 == c3;
	}
	bool isCheck() const
	{
		if (isRookCaptured())
			return false;
		if (r2 == r3)
			return r2 != r1 || (c2 - c1) * (c3 - c1) > 0;
		if (c2 == c3)
			return c2 != c1 || (r2 - r1) * (r3 - r1) > 0;
		return false;
	}
	bool blackCanMove() const
	{
		State nst = *this;
		for (nst.r3 = r3 - 1; nst.r3 <= r3 + 1; nst.r3++)
			for (nst.c3 = c3 - 1; nst.c3 <= c3 + 1; nst.c3++)
				if ((nst.r3 != r3 || nst.c3 != c3) && nst.isValid() && !nst.isCheck())
					return true;
		return false;
	}
	bool isMate() const
	{
		return isCheck() && !blackCanMove();
	}
	bool isStalemate() const
	{
		return !isCheck() && !blackCanMove();
	}
	int getIdx() const
	{
		int idx = 0;
		for (int x : {r1, c1, r2, c2, r3, c3})
			idx = 8 * idx + x;
		return idx;
	}
};

VI gr[N][2];
int cntEdges[N];
int d[N][2];

void solve()
{
	State st = {-1, -1, -1, -1, -1, -1};
	FOR(i, 0, 8)
	{
		string s;
		cin >> s;
		FOR(j, 0, 8)
		{
			if (s[j] == 'W')
			{
				st.r1 = i;
				st.c1 = j;
			}
			else if (s[j] == 'R')
			{
				st.r2 = i;
				st.c2 = j;
			}
			else if (s[j] == 'B')
			{
				st.r3 = i;
				st.c3 = j;
			}
		}
	}
	assert(st.isValid() && !st.isCheck());
	int ans = d[st.getIdx()][0];
	assert(ans != INF);
	cout << ans << "\n";
}

void precalc()
{
	queue<pair<int, int>> q;
	FOR(i, 0, N)
		FOR(j, 0, 2)
			d[i][j] = INF;
	FOR(r1, 0, 8) FOR(c1, 0, 8)
	FOR(r2, 0, 8) FOR(c2, 0, 8)
	FOR(r3, 0, 8) FOR(c3, 0, 8)
	{
		State st = {r1, c1, r2, c2, r3, c3};
		if (!st.isValid())
			continue;
		int idx = st.getIdx();
		if (st.isMate())
		{
			d[idx][1] = 0;
			q.push({idx, 1});
			continue;
		}
		if (st.isStalemate() || st.isRookCaptured())
			continue;
		State nst = st;
		// White moves
		// White king moves
		for (nst.r1 = r1 - 1; nst.r1 <= r1 + 1; nst.r1++)
		{
			for (nst.c1 = c1 - 1; nst.c1 <= c1 + 1; nst.c1++)
			{
				if ((nst.r1 != r1 || nst.c1 != c1) && nst.isValid())
				{
					gr[nst.getIdx()][1].PB(idx);
				}
			}
		}
		// White rook moves
		nst = st;
		for (nst.r2 = 0; nst.r2 < 8; nst.r2++)
		{
			if (nst.r2 != r2 && (c2 != c1 || (r2 - r1) * (nst.r2 - r1) > 0))
			{
				gr[nst.getIdx()][1].PB(idx);
			}
		}
		nst = st;
		for (nst.c2 = 0; nst.c2 < 8; nst.c2++)
		{
			if (nst.c2 != c2 && (r2 != r1 || (c2 - c1) * (nst.c2 - c1) > 0))
			{
				gr[nst.getIdx()][1].PB(idx);
			}
		}
		nst = st;
		// Black moves
		// Black king moves
		for (nst.r3 = r3 - 1; nst.r3 <= r3 + 1; nst.r3++)
		{
			for (nst.c3 = c3 - 1; nst.c3 <= c3 + 1; nst.c3++)
			{
				if ((nst.r3 != r3 || nst.c3 != c3) && nst.isValid() && !nst.isCheck())
				{
					gr[nst.getIdx()][0].PB(idx);
					cntEdges[idx]++;
				}
			}
		}
	}
	while (!q.empty())
	{
		auto [v, p] = q.front();
		q.pop();
		for (int to : gr[v][p])
		{
			if (p)
			{
				if (d[to][0] == INF)
				{
					d[to][0] = d[v][1] + 1;
					q.push({to, 0});
				}
			}
			else
			{
				cntEdges[to]--;
				if (cntEdges[to] == 0)
				{
					d[to][1] = d[v][0];
					q.push({to, 1});
				}
			}
		}
	}
}

int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
	cout << fixed << setprecision(15);
	precalc();
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 140ms
memory: 58772kb

input:

2
........
........
........
........
........
.......W
R.......
.......B

....B...
........
..W.....
........
.....R..
........
........
........


output:

1
2

result:

ok 2 number(s): "1 2"

Test #2:

score: 0
Accepted
time: 154ms
memory: 58704kb

input:

10
........
........
........
..R.....
....W...
........
.B......
........

.......B
........
...R....
........
........
........
W.......
........

........
.W...B..
........
........
..R.....
........
........
........

.W...R..
........
........
........
......B.
........
........
........

........

output:

7
10
9
11
11
12
11
12
14
7

result:

ok 10 numbers

Test #3:

score: 0
Accepted
time: 152ms
memory: 59040kb

input:

10
........
...B....
........
......R.
........
........
..W.....
........

W....B..
........
........
........
.R......
........
........
........

....R...
........
..B.....
........
........
........
........
.....W..

.R......
........
........
........
..B.....
........
........
W.......

........

output:

12
9
14
13
7
7
11
13
7
7

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 134ms
memory: 58704kb

input:

10
..B.....
........
..W.R...
........
........
........
........
........

........
........
........
........
........
..W.....
...R....
..B.....

........
........
..R.....
........
........
..W.....
........
..B.....

..B.....
...R....
W.......
........
........
........
........
........

B.......

output:

1
3
3
6
2
16
16
13
7
13

result:

ok 10 numbers

Test #5:

score: 0
Accepted
time: 139ms
memory: 58708kb

input:

10
.R......
..W..B..
........
........
........
........
........
........

........
........
......W.
........
........
........
...B....
....R...

....W...
........
.......B
........
.....R..
........
........
........

........
........
........
........
.......R
....B...
........
.W......

........

output:

8
12
9
10
11
11
14
10
7
14

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 154ms
memory: 58748kb

input:

10
........
......W.
........
..R.....
...B....
........
........
........

........
........
........
........
....R...
.......B
...W....
........

........
...B....
........
........
........
........
......W.
.....R..

W.......
........
..B.....
........
........
........
.R......
........

........

output:

15
6
13
14
11
10
13
12
7
11

result:

ok 10 numbers

Test #7:

score: 0
Accepted
time: 153ms
memory: 59024kb

input:

10
........
..W.....
....R...
........
........
B.......
........
........

........
........
...W....
.......B
........
.R......
........
........

........
........
W......R
........
........
........
B.......
........

........
........
........
........
R....W..
........
...B....
........

........

output:

8
8
6
10
8
15
4
6
10
11

result:

ok 10 numbers

Test #8:

score: 0
Accepted
time: 157ms
memory: 58744kb

input:

10
........
...B....
........
........
........
R.......
...W....
........

....B...
........
.....R..
..W.....
........
........
........
........

R...W...
........
........
........
........
.B......
........
........

........
........
........
.......W
........
.....R..
......B.
........

........

output:

12
2
12
5
14
5
1
11
10
8

result:

ok 10 numbers

Test #9:

score: 0
Accepted
time: 153ms
memory: 59040kb

input:

10
....B...
........
..W.....
.......R
........
........
........
........

........
........
..W.....
........
R.......
........
........
......B.

.....R..
........
........
.......B
........
........
........
.......W

........
.W......
........
........
........
..R.....
.B......
........

.B......

output:

7
9
9
9
5
12
13
7
9
14

result:

ok 10 numbers