滴滴2017秋招笔试地下迷宫

发表于   |  

##题目描述

小青蛙有一天不小心落入了一个地下迷宫，小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。为了让问题简单，假设这是一个n*m的迷宫。迷宫每个位置为0或者1. 0代表这个位置有障碍物，小青蛙到达不了这个位置；1代表小青蛙可以达到的位置。小青蛙初始在(0,0)位置。地下迷宫的出口在(0,m-1)(保证这两个位置都是1，并且保证一定有起点到终点可达的路径)。小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值。向上爬一个单位距离需要消耗3个体力值，向下移动不消耗体力值。当小青蛙的体力值等于0时候还没有到达出口，小青蛙将无法逃离迷宫。现在需要你帮助小青蛙计算出能否用今生的体力值跳出迷宫（即达到(0,m-1)的位置

输入：

输入 n+1行：
第一行为3个整数n,m(3<=m,n<=10),P(1<=P<=100)
接下来的n行：
每行m个0或者1，以空格分隔
输出：
如果能逃离迷宫，则输出一行体力消耗最小的路径，输出格式见样例所示；如果不能逃离迷宫，则输出“Can not escape!”。
测试数据保证答案唯一
输入例子：

  • 4 4 10
  • 1 0 0 1
  • 1 1 0 1
  • 0 1 1 1
  • 0 0 1 1

输出例子：

[0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3]

思路：层次遍历（这个思想真的蛮重要的..），每次更新最佳值，直到找到了终点，个人感觉比 dfs 好使..（也有 dfs 代码）。后来做的乐视那个蚂蚱跳跃的题目也是如此，过几天忙过去在更新上来.做题的时候一定要先想思路，别急着代码..磨刀不误砍柴工！

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
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 * @author houweitao
 * @date 2016年9月18日下午2:59:03
 */

// 4 4 10
// 1 0 0 1
// 1 1 0 1
// 0 1 1 1
// 0 0 1 1

public class Main {
	public static void main(String[] args) {
		Main main = new Main();
		main.init();
	}

	private void init() {
		Scanner scanner = new Scanner(System.in);
		String[] first = scanner.nextLine().split(" ");

		int n = Integer.valueOf(first[0]);
		int m = Integer.valueOf(first[1]);
		int have = Integer.valueOf(first[2]);

		int[][] map = new int[n][m];

		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				map[i][j] = scanner.nextInt();
			}
		}
		forgEscapeBFS(map, have);

		forgEscapeDFS(map, have);
	}

	void forgEscapeBFS(int[][] map, int have) {
		int m = map[0].length;

		Map<Point, Point> record = new HashMap<>();
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				if (map[i][j] == 1) {
					Point cur = new Point(i, j, Integer.MAX_VALUE);
					record.put(cur, cur);
				}
			}
		}
		Point end = new Point(0, m - 1, 0);

		Map<Point, Point> leaf = new HashMap<>();
		record.put(end, end);
		leaf.put(end, end);

		while (!leaf.isEmpty()) {
			Map<Point, Point> tmp = new HashMap<>();
			for (Map.Entry<Point, Point> entry : leaf.entrySet()) {
				Point point = entry.getValue();
				int x = point.x, y = point.y;
				help(x, y, point, tmp, map, record);
			}
			leaf = tmp;
		}

		Point getStart = new Point(0, 0, Integer.MAX_VALUE);
		Point start = record.get(getStart);

		if (have >= start.need) {
			StringBuffer sb = new StringBuffer();
			while (start != null) {
				sb.append(start + ",");
				start = start.next;
			}
			System.out.println(sb.toString().substring(0, sb.toString().length() - 1));
		} else
			System.out.println("can not secape");
	}

	private void help(int x, int y, Point point, Map<Point, Point> tmp, int[][] map, Map<Point, Point> record) {
		doubleHelp(x + 1, y, 3, point, tmp, map, record);
		doubleHelp(x - 1, y, 0, point, tmp, map, record);
		doubleHelp(x, y + 1, 1, point, tmp, map, record);
		doubleHelp(x, y - 1, 1, point, tmp, map, record);
	}

	private void doubleHelp(int x, int y, int now, Point point, Map<Point, Point> tmp, int[][] map,
			Map<Point, Point> record) {
		if (in(map, x, y) && map[x][y] == 1) {
			now = point.need + now;
			Point seed = new Point(x, y, now);
			if (now < record.get(seed).need) {
				boolean judge = true;
				if (tmp.containsKey(seed))
					if (now > tmp.get(seed).need)
						judge = false;

				if (judge) {
					tmp.put(seed, record.get(seed));
					record.get(seed).next = point;
					record.get(seed).need = now;
				}
			}
		}
	}

	private boolean in(int[][] map, int x, int y) {
		if (x >= 0 && x < map.length && y >= 0 && y < map[0].length)
			return true;
		else
			return false;

	}

	class Point {
		int x;
		int y;
		int need;
		Point next;

		Point(int x, int y, int need) {
			this.x = x;
			this.y = y;
			this.need = need;
		}

		@Override
		public String toString() {
			return "[" + x + "," + y + "]";
		}

		@Override
		public int hashCode() {
			return x + y;
		}

		@Override
		public boolean equals(Object obj) {
			if (obj instanceof Point) {
				Point o = (Point) obj;
				return o.x == x && o.y == y;
			}
			return false;
		}
	}

	// -------------

	int cost = Integer.MAX_VALUE;
	List<Point> finalPath = new ArrayList<>();

	void forgEscapeDFS(int[][] map, int have) {
		List<Point> tmp = new ArrayList<>();
		Set<Point> set = new HashSet<>();

		// dfs(0, 0, 0, map, tmp, set);
		dfs(0, 0, 0, map, tmp);
		System.out.println(finalPath);
	}

	private void dfs(int x, int y, int curCost, int[][] map, List<Point> tmp, Set<Point> set) {
		if (!in(map, x, y) || map[x][y] == 0) {
			return;
		} else if (x == 0 && y == map[0].length - 1) {
			Point cur = new Point(x, y, 1);
			tmp.add(cur);
			System.out.println(curCost + ": " + tmp);
			if (curCost < cost) {
				finalPath = new ArrayList<>(tmp);
			}
			tmp.remove(tmp.size() - 1);
		} else {
			Point cur = new Point(x, y, 1);
			if (!set.contains(cur)) {
				set.add(cur);
				tmp.add(cur);

				dfs(x + 1, y, curCost, map, tmp, set);
				dfs(x - 1, y, curCost + 3, map, tmp, set);
				dfs(x, y + 1, curCost + 1, map, tmp, set);
				dfs(x, y - 1, curCost + 1, map, tmp, set);

				tmp.remove(tmp.size() - 1);
				set.remove(cur);
			}
		}
	}

	// 不用 set 判断。更加节省空间和时间 2016年09月18日18:53:16
	private void dfs(int x, int y, int curCost, int[][] map, List<Point> tmp) {
		if (!in(map, x, y) || map[x][y] == 0) {
			return;
		} else if (x == 0 && y == map[0].length - 1) {
			Point cur = new Point(x, y, 1);
			tmp.add(cur);
			System.out.println(curCost + ": " + tmp);
			if (curCost < cost) {
				finalPath = new ArrayList<>(tmp);
			}
			tmp.remove(tmp.size() - 1);
		} else {
			Point cur = new Point(x, y, 1);
			map[x][y] = 0;
			tmp.add(cur);

			dfs(x + 1, y, curCost, map, tmp);
			dfs(x - 1, y, curCost + 3, map, tmp);
			dfs(x, y + 1, curCost + 1, map, tmp);
			dfs(x, y - 1, curCost + 1, map, tmp);

			tmp.remove(tmp.size() - 1);
			map[x][y] = 1;
		}
	}

}

2016年09月20日01:05:30