The Solver class has a single static method called solve that you must implement. It should behave as follows:

? It takes a single char[][] argument which I have called grid. The grid is a square array (every row and every column have the same size), and each cell contains either s, f, *, or (space character).

? You must find a shortest path (there may be more than one so any shortest path is correct) from the s to the f, while avoiding all the * characters. ? You return the path as a string consisting solely of U, D, L, and R characters. ? U moves you up one row. So if you are currently at grid[3][7], U moves you to grid[2][7].

? D moves you down one row. So if you are currently at grid[3][7], D moves you to grid[4][7]. ? L moves you left one column. So if you are currently at grid[3][7], L moves you to grid[3][6].

? R moves you right one column. So if you are currently at grid[3][7], R moves you to grid[3][8].

you want to make use of the books Graph class and BreadthFirstPaths class to solve this. This means you will need to find a way to translate the problem into a graph problem, run BFS on the graph, and then translate the result from the BFS back into a sequence of U, D, L, and R

~~~~~~~~~~~

package hw5;

public class Solver {

public static String solve(char[][] grid) {

// TODO

/*

* 1. Construct a graph using grid

* 2. Use Breadth first search to find shortest path from start to finish

* 3. Return the sequence of moves to get from start to finish

*/

// Hardcoded solution to toyTest

return "RRRDDDDDDDDDRRRRRR";

}

}

here is the graph class below:

~~~~~

public class Graph {

private static final String NEWLINE = System.getProperty("line.separator");

private final int V;

private int E;

private Bag[] adj;

/**

* Initializes an empty graph with {@code V} vertices and 0 edges.

* param V the number of vertices

*

* @param V number of vertices

* @throws IllegalArgumentException if {@code V < 0}

*/

public Graph(int V) {

if (V < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");

this.V = V;

this.E = 0;

adj = (Bag[]) new Bag[V];

for (int v = 0; v < V; v++) {

adj[v] = new Bag();

}

}

/**

* Initializes a new graph that is a deep copy of {@code G}.

*

* @param G the graph to copy

*/

public Graph(Graph G) {

this(G.V());

this.E = G.E();

for (int v = 0; v < G.V(); v++) {

// reverse so that adjacency list is in same order as original

Stack reverse = new Stack();

for (int w : G.adj[v]) {

reverse.push(w);

}

for (int w : reverse) {

adj[v].add(w);

}

}

}

/**

* Returns the number of vertices in this graph.

*

* @return the number of vertices in this graph

*/

public int V() {

return V;

}

/**

* Returns the number of edges in this graph.

*

* @return the number of edges in this graph

*/

public int E() {

return E;

}

// throw an IllegalArgumentException unless {@code 0 <= v < V}

private void validateVertex(int v) {

if (v < 0 || v >= V)

throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));

}

/**

* Adds the undirected edge v-w to this graph.

*

* @param v one vertex in the edge

* @param w the other vertex in the edge

* @throws IllegalArgumentException unless both {@code 0 <= v < V} and {@code 0 <= w < V}

*/

public void addEdge(int v, int w) {

validateVertex(v);

validateVertex(w);

E++;

adj[v].add(w);

adj[w].add(v);

}

/**

* Returns the vertices adjacent to vertex {@code v}.

*

* @param v the vertex

* @return the vertices adjacent to vertex {@code v}, as an iterable

* @throws IllegalArgumentException unless {@code 0 <= v < V}

*/

public Iterable adj(int v) {

validateVertex(v);

return adj[v];

}

/**

* Returns the degree of vertex {@code v}.

*

* @param v the vertex

* @return the degree of vertex {@code v}

* @throws IllegalArgumentException unless {@code 0 <= v < V}

*/

public int degree(int v) {

validateVertex(v);

return adj[v].size();

}

/**

* Returns a string representation of this graph.

*

* @return the number of vertices V, followed by the number of edges E,

* followed by the V adjacency lists

*/

public String toString() {

StringBuilder s = new StringBuilder();

s.append(V + " vertices, " + E + " edges " + NEWLINE);

for (int v = 0; v < V; v++) {

s.append(v + ": ");

for (int w : adj[v]) {

s.append(w + " ");

}

s.append(NEWLINE);

}

return s.toString();

}

}