案例研究：九尾问题

import java.util.*;

public class ninetailmodel {
    public final static int number_of_nodes = 512;
    protected abstractgraph<integer>.tree tree; // define a tree

    /** construct a model */
    public ninetailmodel() {
        // create edges
        list<abstractgraph.edge> edges = getedges();

        // create a graph
        unweightedgraph<integer> graph = new unweightedgraph<>(edges, number_of_nodes);

        // obtain a bsf tree rooted at the target node
        tree = graph.bfs(511);
    }

    /** create all edges for the graph */
    private list<abstractgraph.edge> getedges() {
        list<abstractgraph.edge> edges = new arraylist<>(); // store edges

        for (int u = 0; u < number_of_nodes; u++) {
            for (int k = 0; k < 9; k++) {
                char[] node = getnode(u); // get the node for vertex u
                if (node[k] == 'h') {
                    int v = getflippednode(node, k);
                    // add edge (v, u) for a legal move from node u to node v
                    edges.add(new abstractgraph.edge(v, u));
                }
            }
        }

        return edges;
    }

    public static int getflippednode(char[] node, int position) {
        int row = position / 3;
        int column = position % 3;

        flipacell(node, row, column);
        flipacell(node, row - 1, column);
        flipacell(node, row + 1, column);
        flipacell(node, row, column - 1);
        flipacell(node, row, column + 1);

        return getindex(node);
    }

    public static void flipacell(char[] node, int row, int column) {
        if (row >= 0 && row <= 2 && column >= 0 && column <= 2) {
            // within the boundary
            if (node[row * 3 + column] == 'h')
                node[row * 3 + column] = 't'; // flip from h to t
            else
                node[row * 3 + column] = 'h'; // flip from t to h
            }
    }

    public static int getindex(char[] node) {
        int result = 0;

        for (int i = 0; i < 9; i++)
            if (node[i] == 't')
                result = result * 2 + 1;
            else
                result = result * 2 + 0;

        return result;
    }

    public static char[] getnode(int index) {
        char[] result = new char[9];

        for (int i = 0; i < 9; i++) {
            int digit = index % 2;
            if (digit == 0)
                result[8 - i] = 'h';
            else
                result[8 - i] = 't';
            index = index / 2;
        }

        return result;
    }

    public list<integer> getshortestpath(int nodeindex) {
        return tree.getpath(nodeindex);
    }

    public static void printnode(char[] node) {
        for (int i = 0; i < 9; i++)
            if (i % 3 != 2)
                system.out.print(node[i]);
            else
                system.out.println(node[i]);

        system.out.println();
    }
}

import java.util.Scanner;

public class NineTail {

    public static void main(String[] args) {
        // Prompt the user to enter nine coins' Hs and Ts
        System.out.print("Enter the initial nine coins Hs and Ts: ");
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        char[] initialNode = s.toCharArray();

        NineTailModel model = new NineTailModel();
        java.util.List<Integer> path = model.getShortestPath(NineTailModel.getIndex(initialNode));

        System.out.println("The steps to flip the coins are ");
        for (int i = 0; i < path.size(); i++)
            NineTailModel.printNode(NineTailModel.getNode(path.get(i).intValue()));
    }

}