QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#768501#7781. Sheep Eat WolvesmobbbWA 0ms3792kbC++201.1kb2024-11-21 11:24:502024-11-21 11:24:51

Judging History

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

  • [2024-11-21 11:24:51]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3792kb
  • [2024-11-21 11:24:50]
  • 提交

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 && u != 0) {
				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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3724kb

input:

4 4 3 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

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

input:

3 5 2 0

output:

3

result:

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