QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#242989 | #7331. The Catcher in the Rye | PetroTarnavskyi# | RE | 0ms | 0kb | C++20 | 3.3kb | 2023-11-07 19:24:30 | 2023-11-07 19:24:31 |
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
2 10 3 4 3 1 1 1 21 5 12 4 4 3 4