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

/* SI 335 Spring 2013
 * Project 3
 * YOUR NAME HERE
 */
 
import java.util.*;
import java.io.*;
 
public class solvemaze {
  
  /* This function takes in a 2D-array that stores a maze description,
     and returns a list of "moves" to make in order to solve the maze.
   */
  static List<Character> calcMoves(char[][] maze) {
    // THIS IS THE FUNCTION YOU NEED TO RE-WRITE!
    // Width and height calculated from maze size, minus borders
    int w = maze.length - 2;
    int h = maze[0].length - 2;
 
    // Start (curY, curX) at the starting position
    int curY = 1;
    int curX = 0;
 
    // The solution here is terrible: it just randomly mills about until
    // it happens upon the end or it runs out of points.
    ArrayList<Character> moves = new ArrayList<Character>();
    Random rgen = new Random();
    while (moves.size() < 4*h*w) {
      int nextY = curY;
      int nextX = curX;
      char nextMove;
      // randomly choose a direction
      if (rgen.nextBoolean()) {
        // go left/right
        if (rgen.nextBoolean()) {
          nextX -= 1;
          nextMove = 'L';
        }
        else {
          nextX += 1;
          nextMove = 'R';
        }
      }
      else {
        // go up/down
        if (rgen.nextBoolean()) {
          nextY -= 1;
          nextMove = 'U';
        }
        else {
          nextY += 1;
          nextMove = 'D';
        }
      }
      if (nextX < 0 || nextX > w+1 || maze[nextY][nextX] == 'X') {
        // illegal move; give up and try another.
        continue;
      }
      moves.add(nextMove);
      curY = nextY;
      curX = nextX;
    }
 
    return moves;
  }
 
  /* Checks whether a row of text contains only valid maze characters */
  static boolean validRow(String row) {
    // YOU DON'T NEED TO CHANGE THIS FUNCTION.
    for (int i=0; i < row.length(); ++i) {
      if (" OX".indexOf(row.charAt(i)) < 0) return false;
    }
    return true;
  }
 
  /* Reads in a maze into a double array of chars. */
  static char[][] readMaze(InputStream in) throws IOException {
    // YOU DON'T NEED TO CHANGE THIS FUNCTION.
    BufferedReader bin = new BufferedReader(new InputStreamReader(in));
    int width = 0;
    String line;
    ArrayList<String> rows = new ArrayList<String>();
    while ((line = bin.readLine()) != null) {
      if (! validRow(line)) {
        throw new IOException("Invalid maze characters in row: " + line);
      }
      // dirty rtrim
      line = ("!" + line).trim().substring(1);
      rows.add(line);
      if (line.length() > width) width = line.length();
    }
    int height = rows.size();
    assert height >= 2;
    assert width >= 2;
    char[][] maze = new char[height][width];
    for (int i=0; i<height; ++i) {
      Arrays.fill(maze[i], ' ');
      String row = rows.get(i);
      row.getChars(0, row.length(), maze[i], 0);
    }
    return maze;
  }
 
  /* Writes the moves in the list to standard out, one per line. */
  static void writeMoves(List<Character> moves) {
    for (char m : moves) {
      System.out.println(m);
    }
  }
 
  public static void main(String[] args) {
    // THIS IS THE MAIN METHOD. YOU DON'T NEED TO CHANGE IT.
    char[][] maze = null;
    try{ maze = readMaze(System.in); }
    catch(IOException e) { e.printStackTrace(); System.exit(1); }
    List<Character> moves = calcMoves(maze);
    writeMoves(moves);
  }
}