Pocket Gems 两轮电面.

1. import java.util.*;
   
2. 
   
3. class Main {
   
4.   public static void main(String[] args) {
   
5.     Robot r = new Robot();
   
6.     char[][] maze = {
   
7.       {'T', 'T', 'T', 'F'},
   
8.       {'F', 'T', 'F', 'T'},
   
9.       {'F', 'T', 'T', 'T'}
   
10.     };
    
11.     List<String> res = r.findPath(maze, 1, 1);
    
12.     System.out.println(String.join(" ", res));
    
13.   }
    
14. }
    
15. 
    
16. class Robot {
    
17.   private List<String> path;
    
18.   private final Map<Integer, String> dirMap;
    
19.   private int count;
    
20.   Robot() {
    
21.     this.dirMap = new HashMap<>();
    
22.     dirMap.put(0, "up");
    
23.     dirMap.put(1, "right");
    
24.     dirMap.put(2, "down");
    
25.     dirMap.put(3, "left");
    
26.   }
    
27.   public List<String> findPath(char[][] maze, int x, int y) {
    
28.     path = null;
    
29.     int m = maze.length;
    
30.     int n = maze[0].length;
    
31.     count = 0;
    
32.     for (int i = 0; i < m; i++) {
    
33.       for (int j = 0; j < n; j++) {
    
34.         if (maze[i][j] == 'T') {
    
35.           count++;
    
36.         }
    
37.       }
    
38.     }
    
39.    
    
40.     boolean[][] visited = new boolean[m][n];
    
41.     dfs(maze, x, y, visited, new ArrayList<>(), -1);
    
42.    
    
43.     return path == null ? new ArrayList<String>() : path;
    
44.   }
    
45.   
    
46.   private void dfs(char[][] maze, int x, int y, boolean[][] visited, List<String> curPath, int comingDirection) {
    
47.     int m = maze.length;
    
48.     int n = maze[0].length;
    
49.     visited[x][y] = true;
    
50.     count--;
    
51.    
    
52.     if (count == 0) {
    
53.       if (path == null) {
    
54.         path = curPath;
    
55.       }
    
56.       return;
    
57.     }
    
58.    
    
59.     int[][] dirs = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
    
60.     for (int i = 0; i < 4; i++) {
    
61.       int xx = x + dirs[i][0];
    
62.       int yy = y + dirs[i][1];
    
63.       
    
64.       if (xx < 0 || xx >= m || yy < 0 || yy >= n || visited[xx][yy] || maze[xx][yy] == 'F') {
    
65.         continue;
    
66.       }
    
67.       curPath.add(dirMap.get(i));
    
68.       dfs(maze, xx, yy, visited, curPath, i);
    
69.     }
    
70.    
    
71.     if (comingDirection != -1 && path == null) {
    
72.       curPath.add(dirMap.get((comingDirection + 2) % 4));
    
73.     }
    
74.   }
    
75. }

复制代码

贴个解法https://repl.it/JkZ4/2

补充内容 (2017-7-26 20:44):
大概思路就是纯dfs，记录每次所到点来的方向，在每个路口所有4个方向走完返回前，把一个反方向加到路径里（L71-73)