/*
 * โครงสร้างข้อมูล : ฉบับวาจาวา
 * http://www.cp.eng.chula.ac.th/~somchai/books
 */
package dataStructures;

/**
 * ตัวอย่างการใช้งานแถวคอยเพื่อการค้นหาตามแนวกว้าง
 * @author สมชาย ประสิทธิ์จูตระกูล
 */
public class Examples {

  //----------------------------------------------------
  static class Node {
    int value;
    Node prev;
    Node(int v, Node p) {
      this.value = v;
      this.prev = p;
    }
    public boolean equals(Object o) {
      if (!(o instanceof Node)) return false;
      return this.value == ((Node) o).value;
    }
  }
  public static void bfsM3D2(int target) {
    Set set = new ArraySet(100);
    Queue q = new ArrayQueue(100);
    Node v = new Node(1,null);  // เริ่มด้วย 1
    q.enqueue(v); set.add(v);
    while( !q.isEmpty() ) {
      v = (Node) q.dequeue();
      if (v.value == target) break;
      Node v1 = new Node(v.value/2, v);
      Node v2 = new Node(v.value*3, v);
      if (!set.contains(v1)) {q.enqueue(v1); set.add(v1);} 
      if (!set.contains(v2)) {q.enqueue(v2); set.add(v2);} 
    }
    if (v.value == target) showSolution(v);
  }
  static void showSolution(Node v) {
    if (v.prev != null) {
      showSolution(v.prev);
      System.out.print((v.prev.value / 2 == v.value) ?
                       "/ 2" : "? 3"); 
    } else {
      System.out.print("1 ");
    }
  }
  //----------------------------------------------------
  public static class Pos {
    int row, col;
    Pos(int r, int c) {row = r; col = c;}
  }
  public static void findPath(int[][] map, Pos source, Pos target) {
    map[source.row][source.col] = 0;   // ต้นทาง
    map[target.row][target.col] = -1;  // ปลายทาง
    Queue q = new ArrayQueue(map.length); q.enqueue(source);
    while (!q.isEmpty()) {
      Pos p = (Pos) q.dequeue();
      if (p.row == target.row && p.col == target.col) break;
      expand(map, q, p.row + 1, p.col, map[p.row][p.col]+1);
      expand(map, q, p.row - 1, p.col, map[p.row][p.col]+1);
      expand(map, q, p.row, p.col + 1, map[p.row][p.col]+1);
      expand(map, q, p.row, p.col - 1, map[p.row][p.col]+1);
    }
  }
  static void expand(int[][] map, Queue q, int r, int c, int k) {
    if (r<0 || r>=map.length ||
        c<0 || c>=map[r].length || map[r][c] != 0) return;
    map[r][c] = k;
    q.enqueue(new Pos(r, c));
  }

}