QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#242989#7331. The Catcher in the RyePetroTarnavskyi#RE 0ms0kbC++203.3kb2023-11-07 19:24:302023-11-07 19:24:31

Judging History

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

  • [2023-11-07 19:24:31]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-11-07 19:24:30]
  • 提交

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
	{
		return r2 == r3 || c2 == c3;
	}
	/*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.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;
	}
};

int dp[N][2];

int dfs(State st, int p)
{
	assert(st.isValid());
	int idx = st.getIdx();
	if (dp[idx][p] != -1)
		return dp[idx][p];
	if (st.isRookCaptured())
		return dp[idx][p] = INF;
	State nst = st;
	// Black moves
	if (p)
	{
		int cntValidMoves = 0;
		int& mx = dp[idx][p] = 0;
		// Black king moves
		for (nst.r3 = st.r3 - 1; nst.r3 <= st.r3; nst.r3++)
		{
			for (nst.c3 = st.c3 - 1; nst.c3 <= st.c3; nst.c3++)
			{
				if (nst.r3 != st.r3 && nst.c3 != st.c3 && nst.isValid() && !nst.isCheck())
				{
					cntValidMoves++;
					mx = max(mx, dfs(nst, 0));
				}
			}
		}
		// can move or mate
		if (cntValidMoves > 0 || st.isCheck())
			return mx;
		// stalemate
		return dp[idx][p] = INF;
	}
	int& mn = dp[idx][p] = INF;
	// White king moves
	for (nst.r1 = st.r1 - 1; nst.r1 <= st.r1; nst.r1++)
	{
		for (nst.c1 = st.c1 - 1; nst.c1 <= st.c1; nst.c1++)
		{
			if (nst.r1 != st.r1 && nst.c1 != st.c1 && nst.isValid())
			{
				mn = min(mn, dfs(nst, 1) + 1);
			}
		}
	}
	// White rook moves
	nst = st;
	for (nst.r2 = 0; nst.r2 < 8; nst.r2++)
	{
		if (nst.r2 != st.r2 && (st.c2 != st.c1 || (st.r2 - st.r1) * (nst.r2 - st.r1) > 0))
		{
			mn = min(mn, dfs(nst, 1) + 1);
		}
	}
	for (nst.c2 = 0; nst.c2 < 8; nst.c2++)
	{
		if (nst.c2 != st.c2 && (st.r2 != st.r1 || (st.c2 - st.c1) * (nst.c2 - st.c1) > 0))
		{
			mn = min(mn, dfs(nst, 1) + 1);
		}
	}
	return mn;
}

void solve()
{
	State st;
	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;
			}
		}
	}
	cout << dfs(st, 0) << "\n";
}

int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
	cout << fixed << setprecision(15);
	FOR(i, 0, N)
		FOR(j, 0, 2)
			dp[i][j] = -1;
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

详细

Test #1:

score: 0
Runtime Error

input:

2
10 3 4 3 1 1 1
21 5 12 4 4 3 4

output:


result: