import edu.princeton.cs.algs4.In; //导入依赖的package包/类
public static void main(String[] args) {
    //In in = new In(args[0]);      // input file
    //debug...
    In in = new In("E:\\DCMMC\\Java\\Java\\Algorithms\\tk\\dcmmc\\fundamentals\\Algorithms\\percolation-testing\\"
        + "sedgewick60.txt");

    int n = in.readInt();         // n-by-n percolation system

    // turn on animation mode
    StdDraw.enableDoubleBuffering();

    // repeatedly read in sites to open and draw resulting system
    Percolation perc = new Percolation(n);
    draw(perc, n);
    StdDraw.show();
    StdDraw.pause(DELAY);
    while (!in.isEmpty()) {
        int i = in.readInt();
        int j = in.readInt();
        perc.open(i, j);
        draw(perc, n);
        StdDraw.show();
        StdDraw.pause(DELAY);
    }
}
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
public static void main(String[] args) {

        // create initial board from file
        In in = new In(args[0]);
        int n = in.readInt();
        int[][] blocks = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                blocks[i][j] = in.readInt();
        Board initial = new Board(blocks);

        // solve the puzzle
        Solver solver = new Solver(initial);

        // print solution to standard output
        if (!solver.isSolvable())
            StdOut.println("No solution possible");
        else {
            StdOut.println("Minimum number of moves = " + solver.moves());
            for (Board board : solver.solution())
                StdOut.println(board);
        }
    }
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
public static void main(String[] args) {

        // create initial board from file
        In in = new In(args[0]);
        int n = in.readInt();
        int[][] blocks = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                blocks[i][j] = in.readInt();
        Board initial = new Board(blocks);
        initial = new Board(new int[][] {{0, 1}, {2, 3}});
        StdOut.println(initial.twin());
        /*for (Board b: initial.neighbors()) {
            StdOut.println(b);
        }*/
    }
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
public static void main(String[] args) {
    In in = new In(args[0]);      // input file
    int n = in.readInt();         // n-by-n percolation system

    // turn on animation mode
    StdDraw.enableDoubleBuffering();

    // repeatedly read in sites to open and draw resulting system
    Percolation perc = new Percolation(n);
    draw(perc, n);
    StdDraw.show();
    StdDraw.pause(DELAY);
    while (!in.isEmpty()) {
        int i = in.readInt();
        int j = in.readInt();
        perc.open(i, j);
        draw(perc, n);
        StdDraw.show();
        StdDraw.pause(DELAY);
    }
}
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
/**
 * Initializes a board from the given filename.
 * @param filename the name of the file containing the Boggle board
 */
public BoggleBoard(String filename) {
    In in = new In(filename);
    m = in.readInt();
    n = in.readInt();
    if (m <= 0) throw new IllegalArgumentException("number of rows must be a positive integer");
    if (n <= 0) throw new IllegalArgumentException("number of columns must be a positive integer");
    board = new char[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            String letter = in.readString().toUpperCase();
            if (letter.equals("QU"))
                board[i][j] = 'Q';
            else if (letter.length() != 1)
                throw new IllegalArgumentException("invalid character: " + letter);
            else if (ALPHABET.indexOf(letter) == -1)
                throw new IllegalArgumentException("invalid character: " + letter);
            else 
                board[i][j] = letter.charAt(0);
        }
    }
}
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
public static void main(String[] args) {

        // for each command-line argument
        for (String filename : args) {

            // read in the board specified in the filename
            In in = new In(filename);
            int n = in.readInt();
            int[][] tiles = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    tiles[i][j] = in.readInt();
                }
            }

            // solve the slider puzzle
            Board initial = new Board(tiles);
            Solver solver = new Solver(initial);
            StdOut.println(filename + ": " + solver.moves());
        }
    }
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
public BaseballElimination(String filename) {
	In in = new In(filename);
	this.numberOfTeams = Integer.parseInt(in.readLine());
	teams = new Hashtable<String, InfoOfTeam>();
	g = new int[numberOfTeams][numberOfTeams];
	id2TeamName = new String[numberOfTeams];	
	v2id = new Hashtable<Integer, Integer>();
	
	int id  = 0;
	while (in.hasNextLine()) {
		String line = in.readLine().trim();
		String[] tokens = line.split(" +");
		String key = tokens[0];
		int wins = Integer.parseInt(tokens[1]);
		int loss = Integer.parseInt(tokens[2]);
		int left = Integer.parseInt(tokens[3]);
		teams.put(key, new InfoOfTeam(id, wins, loss, left));
		id2TeamName[id] = key;
		
		for(int i = 0; i < this.numberOfTeams; i++) {
			g[id][i] = Integer.parseInt(tokens[4+i]);
		}
		id++;
	}
}
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
public static void main(String[] args) {
    String filename = args[0];
    In in = new In(filename);
    int n = in.readInt();
    int i = 0;
    int[][] tiles = new int[n][n];
    while (!in.isEmpty()) {
        tiles[i/n][i%n] = in.readInt();
        i++;
    }
    try{
        Solver sv = new Solver(new Board(tiles));
        StdOut.println("Minimum number of moves = "+sv.moves());
        for(Board b : sv.solution())
            StdOut.print(b);
    }catch(java.lang.IllegalArgumentException e){
        StdOut.println(e.getMessage());
    }

}
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
public static void main(String[] args) {
    String filename = args[0];
    In in = new In(filename);
    int n = in.readInt();
    int i = 0;
    int[][] tiles = new int[n][n];
    while (!in.isEmpty()) {
        tiles[i/n][i%n] = in.readInt();
        i++;
    }
    Board b = new Board(tiles);
    StdOut.print(b);
    StdOut.println("Hamming  = "+ b.hamming());
    StdOut.println("Manhattan = "+ b.manhattan());
    StdOut.println("isGoal = "+ b.isGoal());
    StdOut.println("isSolvable = "+  b.isSolvable());
}
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
private static void simulateFromFile(String filename) {
    In in = new In(filename);
    int n = in.readInt();
    Percolation perc = new Percolation(n);

    // turn on animation mode
    StdDraw.enableDoubleBuffering();

    // repeatedly read in sites to open and draw resulting system
    draw(perc, n);
    StdDraw.show();
    StdDraw.pause(DELAY);

    while (!in.isEmpty()) {
        int i = in.readInt();
        int j = in.readInt();
        perc.open(i - 1, j - 1);
        draw(perc, n);
        StdDraw.show();
        StdDraw.pause(DELAY);
    }
}
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
public static void main(String[] args) {
    for (int i = 0; i < args.length; i++) {   
        In in = new In(args[i]);
        BinaryTreeNode root = BinaryTreeNode.deserialize(in.readAll().trim());
        BinaryTreeNode leftLeaf = root;
        while(leftLeaf.left != null) {
            leftLeaf = leftLeaf.left;
        }
        BinaryTreeNode rightLeaf = root;
        while(rightLeaf.right != null) {
            rightLeaf = rightLeaf.right;
        }
        //LinearLCA llca = new LinearLCA(root);
        RecursiveLCA rlca = new RecursiveLCA(root);
        //System.out.println(llca.query(root, leftLeaf) == root);
        System.out.println(rlca.query(root, leftLeaf) == root);
        //System.out.println(llca.query(root, rightLeaf) == root);
        System.out.println(rlca.query(root, rightLeaf) == root);
        //System.out.println(llca.query(rightLeaf, leftLeaf) == root);
        System.out.println(rlca.query(rightLeaf, leftLeaf) == root);
    }
}
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
/**
 * Unit tests the {@code AcyclicSP} data type.
 *
 * @param args the command-line arguments
 */
public static void main(String[] args) {
  In in = new In(args[0]);
  int s = Integer.parseInt(args[1]);
  EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);

  // find shortest path from s to each other vertex in DAG
  AcyclicSP sp = new AcyclicSP(G, s);
  for (int v = 0; v < G.V(); v++) {
    if (sp.hasPathTo(v)) {
      StdOut.printf("%d to %d (%.2f)  ", s, v, sp.distTo(v));
      for (DirectedEdge e : sp.pathTo(v)) {
        StdOut.print(e + "   ");
      }
      StdOut.println();
    }
    else {
      StdOut.printf("%d to %d         no path\n", s, v);
    }
  }
}
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
/**
 * Unit tests the <tt>DirectedDFS</tt> data type.
 */
public static void main(String[] args) {

    // read in digraph from command-line argument
    In in = new In(args[0]);
    Digraph G = new Digraph(in);

    // read in sources from command-line arguments
    Bag<Integer> sources = new Bag<Integer>();
    for (int i = 1; i < args.length; i++) {
        int s = Integer.parseInt(args[i]);
        sources.add(s);
    }

    // multiple-source reachability
    DirectedDFS dfs = new DirectedDFS(G, sources);

    // print out vertices reachable from sources
    for (int v = 0; v < G.V(); v++) {
        if (dfs.marked(v)) StdOut.print(v + " ");
    }
    StdOut.println();
}
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
/**
 * Unit tests the {@code AcyclicSP} data type.
 *
 * @param args the command-line arguments
 */
public static void main(String[] args) {
  In in = new In(args[0]);
  int s = Integer.parseInt(args[1]);
  EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);

  // find shortest path from s to each other vertex in DAG
  AcyclicLP sp = new AcyclicLP(G, s);
  for (int v = 0; v < G.V(); v++) {
    if (sp.hasPathTo(v)) {
      StdOut.printf("%d to %d (%.2f)  ", s, v, sp.distTo(v));
      for (DirectedEdge e : sp.pathTo(v)) {
        StdOut.print(e + "   ");
      }
      StdOut.println();
    }
    else {
      StdOut.printf("%d to %d         no path\n", s, v);
    }
  }
}
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
/**
 * Unit tests the <tt>BreadthFirstDirectedPaths</tt> data type.
 */
public static void main(String[] args) {
    In in = new In(args[0]);
    Digraph G = new Digraph(in);
    // StdOut.println(G);

    int s = Integer.parseInt(args[1]);
    BreadthFirstDirectedPaths bfs = new BreadthFirstDirectedPaths(G, s);

    for (int v = 0; v < G.V(); v++) {
        if (bfs.hasPathTo(v)) {
            StdOut.printf("%d to %d (%d):  ", s, v, bfs.distTo(v));
            for (int x : bfs.pathTo(v)) {
                if (x == s) StdOut.print(x);
                else        StdOut.print("->" + x);
            }
            StdOut.println();
        }

        else {
            StdOut.printf("%d to %d (-):  not connected\n", s, v);
        }

    }
}
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
/**
 * Unit tests the <tt>DirectedCycle</tt> data type.
 */
public static void main(String[] args) {
    In in = new In(args[0]);
    Digraph G = new Digraph(in);

    DirectedCycle finder = new DirectedCycle(G);
    if (finder.hasCycle()) {
        StdOut.print("Directed cycle: ");
        for (int v : finder.cycle()) {
            StdOut.print(v + " ");
        }
        StdOut.println();
    }

    else {
        StdOut.println("No directed cycle");
    }
    StdOut.println();
}
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
/**
 * simple unit tests
 * @param args
 */
public static void main(String[] args) {
    /*test serialization deserialization*/
    for (int i = 0; i < args.length; i++) {
        System.out.println("processing " + args[i]);
        In in = new In(args[i]);
        System.out.println(serialize(deserialize(in.readAll().trim())));   
    }        
    System.out.println(serialize(deserialize("1,2,3")));
    System.out.println(serialize(deserialize("1,2,#,3,#")));
    /*test Euler tour*/
    BinaryTreeNode test = new BinaryTreeNode(0);
    test.left = new BinaryTreeNode(1);
    test.right = new BinaryTreeNode(2);
    BinaryTreeNode[] eulerTour = BinaryTreeNode.EulerTour(test);
    System.out.println(eulerTour[0] == test);
    System.out.println(eulerTour[1] == test.left);
    System.out.println(eulerTour[2] == test);
    System.out.println(eulerTour[3] == test.right);
    System.out.println(eulerTour[4] == test);
    /*test levels*/
    Map<BinaryTreeNode, Integer> node2level = BinaryTreeNode.getLevels(test);
    System.out.println(node2level.get(test) == 0);
    System.out.println(node2level.get(test.left) == 1);
    System.out.println(node2level.get(test.right) == 1);
}
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
public static void main(String[] args) {
	In in = new In(args[0]);
	int context = Integer.parseInt(args[1]);
	
	String text = in.readAll().replaceAll("\\s+", " ");
	int N = text.length();
	SuffixArray sa = new SuffixArray(text);
	while (StdIn.hasNextChar()) {
		String q = StdIn.readLine();
		for (int i = sa.rank(q); i < N && sa.select(i).startsWith(q); i++) {
			int from = Math.max(0, sa.index(i) - context);
			int to = Math.min(N-1, from + q.length() + 2*context);
			StdOut.println(text.substring(from,to));
		}
	}
	
}
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
/**
 * Unit tests the {@code DijkstraSP} data type.
 *
 * @param args the command-line arguments
 */
public static void main(String[] args) {
  In in = new In(args[0]);
  EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
  int s = Integer.parseInt(args[1]);

  // compute shortest paths
  DijkstraSP sp = new DijkstraSP(G, s);


  // print shortest path
  for (int t = 0; t < G.V(); t++) {
    if (sp.hasPathTo(t)) {
      StdOut.printf("%d to %d (%.2f)  ", s, t, sp.distTo(t));
      for (DirectedEdge e : sp.pathTo(t)) {
        StdOut.print(e + "   ");
      }
      StdOut.println();
    }
    else {
      StdOut.printf("%d to %d         no path\n", s, t);
    }
  }
}
 

import edu.princeton.cs.algs4.In; //导入依赖的package包/类
/**
 * Unit tests the <tt>DepthFirstPaths</tt> data type.
 */
public static void main(String[] args) {
    In in = new In(args[0]);
    Graph G = new Graph(in);
    int s = Integer.parseInt(args[1]);
    DepthFirstPaths dfs = new DepthFirstPaths(G, s);

    for (int v = 0; v < G.V(); v++) {
        if (dfs.hasPathTo(v)) {
            StdOut.printf("%d to %d:  ", s, v);
            for (int x : dfs.pathTo(v)) {
                if (x == s) StdOut.print(x);
                else        StdOut.print("-" + x);
            }
            StdOut.println();
        }

        else {
            StdOut.printf("%d to %d:  not connected\n", s, v);
        }

    }
}