一道编程题：贪食蛇可以获得的最大分数？

发表于   |  

题目如下：给定一个矩阵，没给点上都有一个整数，取值范围为-1~1000。我们的猪脚贪食蛇从最左侧出发，目的地是最右边的任意一个点。每走过一个点，贪食蛇可以获取位置上的分数。

游戏规则如下：

  • 贪食蛇只可以往上，往下，往右移动；贪食蛇
  • 贪食蛇不可以走回头路：走过的点不可以再走
  • 如果贪食蛇不可以到达目的点，返回-1；可以的话返回可以得到的最大的分数
  • 贪食蛇可以穿越上下边界，比如从下届穿越到上界只是这时候几分要清零
  • 值为1点不可以走

分析：这里应该可以用DFS,BFS这种解法，可是直观上感觉复杂度会很高。因此，这里使用自底向上的动态规划

解法如下：

维护2个表
  • 一个是正常走的点，不包括穿越，这个矩阵的值的求取，自底向上的动态规划。先求最右层的的最佳进入点；然后求次右层的最佳进入点…直到第一层。
  • 一个是穿越走的表（因为穿越后积分清零，因此需要特别讨论）
  • 得到结果后，最后判断第一层的点的最大值是否比其他点的最大值大，如果不是，则不可以到达最右点（此处并不完美，有个小bug是如果前半部分非常大的情况）
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
public class Snake {
    public static void main(String[] args) {
		Snake sg = new Snake();

		int[][] matrix =
//			{ { -1, 4, 5, 1 }, { 2, -1, 2, 4 }, { 3, 3, -1, 3 }, { 4, 2, 1, 2 } };
		{
//			{ 2, 3, -1, 2 }, 
				{ -1, 4, 5, 1 }, { 2, -1, 2, 4 }, { 3, 3, -1, -1 }, { 4, 2, -1, 2 } };
		sg.print(matrix);
		System.out.println(sg.maxPoint(matrix));

		sg.initSystem();
	}

	void initSystem() {
		int n = -1, m = -1;
		Scanner scanner = new Scanner(System.in);
		String str = scanner.nextLine();
		String[] s = str.split(" ");
		n = Integer.valueOf(s[0]);
		m = Integer.valueOf(s[1]);

		int[][] matrix = buildMatrix(scanner, n, m);
//		print(matrix);
		System.out.println(maxPoint(matrix));
	}

	private int[][] buildMatrix(Scanner scanner, int n, int m) {
		int[][] matrix = new int[n][m];

		for (int i = 0; i < n; i++) {
			String str = scanner.nextLine();
			String[] s = str.split(" ");
			for (int j = 0; j < m; j++) {
				matrix[i][j] = Integer.valueOf(s[j]);
			}
		}
		return matrix;
	}

	private void print(int[][] matrix) {
		int m = matrix.length;
		int n = matrix[0].length;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}

	int maxPoint(int[][] matrix) {
		int m = matrix.length;
		int n = matrix[0].length;

		int[][] point = new int[m][n + 1];
		int[][] jumpOut = new int[m][n + 1];

		for (int j = n - 1; j >= 0; j--) {
			for (int i = 0; i < m; i++) {
				if (matrix[i][j] == -1)
					point[i][j] = -1;
				else {
					int cur = 0;
					int up = Integer.MIN_VALUE;
					int down = Integer.MIN_VALUE;
					int jumpUp = -1;
					int jumpDown = -1;
					boolean canUp = false, canDown = false;

					//up
					for (int k = i; k >= 0; k--) {
						if (matrix[k][j] == -1)
							break;
						cur = cur + matrix[k][j];
						int add = point[k][j + 1] > 0 ? point[k][j + 1] : 0;
						up = Math.max(up, cur + add);

						if (k == 0) {
							canUp = true;
						}
					}

					cur = 0;
					//down
					for (int k = i; k < m; k++) {
						if (matrix[k][j] == -1)
							break;

						cur = cur + matrix[k][j];
						int add = point[k][j + 1] > 0 ? point[k][j + 1] : 0;
						down = Math.max(down, cur + add);

						if (k == m - 1)
							canDown = true;
					}

//					System.out.println("(" + i + "," + j + ") : " + canUp + "," + canDown);

					if (canUp) {
						cur = 0;
						for (int k = m - 1; k > i; k--) {
							if (matrix[k][j] == -1)
								break;
							cur = cur + matrix[k][j];
							int add = point[k][j + 1] > 0 ? point[k][j + 1] : 0;
							jumpDown = Math.max(down, cur + add);
						}
					}
					if (canDown) {
						cur = 0;
						for (int k = 0; k < i; k++) {
							if (matrix[k][j] == -1)
								break;
							cur = cur + matrix[k][j];
							int add = point[k][j + 1] > 0 ? point[k][j + 1] : 0;
							jumpUp = Math.max(up, cur + add);
						}
					}

					point[i][j] = Math.max(up, down);
					jumpOut[i][j] = Math.max(jumpUp, jumpDown);
//					if (canUp)
//						point[i][j] = Math.max(point[i][j], point[m - 1][j]);

//					System.out.println("(" + i + "," + j + ")  " + point[i][j]);
				}
			}
		}
//
//		System.out.println("jumpOut");
//		print(jumpOut);
//		System.out.println("point");
//		print(point);
		deal(point, jumpOut);

//		System.out.println("point");
//		print(point);

		if (!canReach(point)) {
			return -1;
		}

		int max = Integer.MIN_VALUE;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				max = Math.max(max, point[i][j]);
//				System.out.print(point[i][j] + " ");
			}
//			System.out.println();
		}
//		System.out.println();
		return max;
	}

	private boolean canReach(int[][] point) {
		int firstMax = -1, otherMax = -1;
		for (int i = 0; i < point.length; i++)
			firstMax = Math.max(firstMax, point[i][0]);

		for (int i = 0; i < point.length; i++) {
			for (int j = 1; j < point[i].length; j++) {
				otherMax = Math.max(otherMax, point[i][j]);
			}
		}

		if (firstMax < otherMax)
			return false;
		else
			return true;
	}

	private void deal(int[][] point, int[][] jump) {
		int m = point.length, n = point[0].length - 1;
		int[][] record = new int[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (point[i][j] == -1)
					jump[i][j] = -1;
				else if (point[i][j] < jump[i][j]) {
					point[i][j] = jump[i][j];
					record[i][j] = 1;
				}
			}
		}

		for (int j = n - 1; j >= 0; j--) {
			for (int i = 0; i < m; i++) {
				if (record[i][j] == 1)
					change(point, i, j);
			}
		}
	}

	private void change(int[][] point, int i, int j) {
		if (!in(point, i, j))
			return;

		int tar = point[i][j];
		if (in(point, i - 1, j)) {
			if (point[i - 1][j] != -1 && point[i - 1][j] < tar) {
				point[i - 1][j] = tar;
				change(point, i - 1, j);
			}
		}
		if (in(point, i + 1, j)) {
			if (point[i + 1][j] != -1 && point[i + 1][j] < tar) {
				point[i + 1][j] = tar;
				change(point, i + 1, j);
			}
		}
		if (in(point, i, j - 1)) {
			if (point[i][j - 1] != -1 && point[i][j - 1] < tar) {
				point[i][j - 1] = tar;
				change(point, i, j - 1);
			}
		}
	}

	private boolean in(int[][] point, int i, int j) {
		if (i >= 0 && i < point.length && j >= 0 && j < point[0].length)
			return true;
		else
			return false;
	}
}

2016年3月18日09:52:53