1  import java.util.*;
  2  
  3  public class WeightedNineTailModel extends NineTailModel {
  4    /** Construct a model */
  5    public WeightedNineTailModel() {
  6      // Create edges
  7      List<WeightedEdge> edges = getEdges();
  8      
  9      // Create a graph
 10      WeightedGraph<Integer> graph = new WeightedGraph<>(
 11        edges, NUMBER_OF_NODES); 
 12  
 13      // Obtain a shortest path tree rooted at the target node
 14      tree = graph.getShortestPath(511);
 15    }
 16  
 17    /** Create all edges for the graph */
 18    private List<WeightedEdge> getEdges() {
 19      // Store edges
 20      List<WeightedEdge> edges = new ArrayList<>(); 
 21  
 22      for (int u = 0; u < NUMBER_OF_NODES; u++) {
 23        for (int k = 0; k < 9; k++) {
 24          char[] node = getNode(u); // Get the node for vertex u
 25          if (node[k] == 'H') {
 26            int v = getFlippedNode(node, k);
 27            int numberOfFlips = getNumberOfFlips(u, v);
 28            
 29            // Add edge (v, u) for a legal move from node u to node v
 30            edges.add(new WeightedEdge(v, u, numberOfFlips));
 31          }
 32        }
 33      }
 34  
 35      return edges;
 36    }
 37    
 38    private static int getNumberOfFlips(int u, int v) {
 39      char[] node1 = getNode(u);
 40      char[] node2 = getNode(v);
 41  
 42      int count = 0; // Count the number of different cells
 43      for (int i = 0; i < node1.length; i++)
 44        if (node1[i] != node2[i]) count++;
 45  
 46      return count;
 47    }
 48  
 49    public int getNumberOfFlips(int u) {
 50      return (int)((WeightedGraph<Integer>.ShortestPathTree)tree)
 51        .getCost(u);
 52    }
 53  }