2019ECNU机试09

发表于 | 分类于 | 评论数： | 热度： ℃
本文字数： 9.2k | 阅读时长 ≈ 8 分钟

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
//通过了给的两个测试点，但可能还有问题
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<vector<string>> arr(10,vector<string>(10));
int sum = 0;
int n, m, p, q;
bool sp = false;//默认是双点策略

void dfs(int x,int y,int _sum) {

	if (x==n&&y==0) {
		if (_sum > sum)
			sum = _sum;
		return;
	}

	int i, j;
	for (i = x;i < n;i++) {
		for (j = y;j < m;j++) {
			if (arr[i][j] != "c") {
				if (j + 1 < m)
					dfs(i, j + 1, _sum);
				else
					dfs(i + 1, 0, _sum);
				continue;
			}

			if (sp) {
				//单点策略
				_sum += p;
				arr[i][j] = "";
				if(j+1<m)
					dfs(i,j+1, _sum);
				else
					dfs(i+1, 0, _sum);
				_sum -= p;
				arr[i][j] = "c";
			}
			else {
				//非单点
				if (j + 1 < m && arr[i][j + 1] == "c") {
					//消右边
					_sum += q;
					arr[i][j] = "";
					arr[i][j+1] = "";
					if(j + 2<m)
						dfs(i, j + 2, _sum);
					else
						dfs(i+1, 0, _sum);
					_sum -= q;
					arr[i][j] = "c";
					arr[i][j + 1] = "c";
				}
				else if (x + 1 < n && arr[i+1][j] == "c") {
					//消下面
					//消右边
					_sum += q;
					arr[i][j] = "";
					arr[i+1][j] = "";
					dfs(i+1, j, _sum);
					_sum -= q;
					arr[i][j] = "c";
					arr[i+1][j] = "c";
				}
				else {
					//只剩一个点
					_sum += p;
					arr[i][j] = "";
					if (j + 1 < m)
						dfs(i, j + 1, _sum);
					else
						dfs(i + 1, 0, _sum);
					_sum -= p;
					arr[i][j] = "c";
				}
				
			}
		}
	}

}

int main() {
	
	scanf("%d%d%d%d", &n, &m, &p, &q);
	int i, j;
	string c;
	for (i = 0;i < n;i++) {
		for (j = 0;j < m;j++) {
			cin >> c;
			arr[i][j] = c;
		}
	}
	
	//用单点代替双点
	if (2 * p > q)
		sp = true;

	dfs(0,0,0);
	cout << sum;

	return 0;
}

----\(˙<>˙)/----赞赏一下吧～