QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#768497#7781. Sheep Eat WolvesmobbbWA 1ms3740kbC++201.1kb2024-11-21 11:23:052024-11-21 11:23:07

Judging History

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

  • [2024-11-21 11:23:07]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3740kb
  • [2024-11-21 11:23:05]
  • 提交

answer

#include <bits/stdc++.h>

#define ll long long

constexpr int N = 101;

int x, y, p, q, dp[N][N][2];// 0, 1

void dfs(int i, int j, int t){
	for (int u = std::max(0, i - p); u <= std::min(x, i + p); u++){
		for (int v = std::max(0, j - p); v <= std::min(y, j + p); v++){
			int change = (i - u) + (j - v);
			if (change > p) {
				continue;
			}
			int r = x - u, c = y - v;
			if (u + q < v) {
				continue;
			}
			if (dp[r][c][t ^ 1] == -1){
				dp[r][c][t ^ 1] = dp[i][j][t] + 1;
				dfs(r, c, t ^ 1);
			}else if (dp[r][c][t ^ 1] > dp[i][j][t] + 1){
				dp[r][c][t ^ 1] = dp[i][j][t] + 1;
				dfs(r, c, t ^ 1);
			}
		}
	}
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> x >> y >> p >> q;
	memset(dp, -1, sizeof(dp));
	dp[x][y][0] = 0;
	dfs(x, y, 0);

	int ans = 1E9;
	for (int i = 0;i <= y; i++){
		if (dp[x][i][1] == -1){
			continue;
		}
		ans = std::min(ans, dp[x][i][1]);
	}
	// std::cout << dp[2][1][1] << '\n';
	if (ans == 1e9){
		std::cout << "-1\n";
	}else{
		std::cout << ans << '\n';
	}


	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3704kb

input:

4 4 3 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

3 5 2 0

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

2 5 1 1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3740kb

input:

1 1 1 0

output:

3

result:

wrong answer 1st numbers differ - expected: '1', found: '3'