import java.util.*;

public class NineTailModel {
  public final static int NUMBER_OF_NODES = 512;
  protected UnweightedGraph<Integer>.SearchTree tree; 

  /** Tworzenie modelu */
  public NineTailModel() {
    // Tworzenie krawędzi
    List<Edge> edges = getEdges();
    
    // Tworzenie grafu
    UnweightedGraph<Integer> graph = new UnweightedGraph<>(
      edges, NUMBER_OF_NODES); 

    // Pobieranie drzewa BSF, którego korzeniem jest węzeł docelowy
    tree = graph.bfs(511);
  }

  /** Pobieranie wszystkich krawędzi grafu */
  private List<Edge> getEdges() {
    List<Edge> edges =
      new ArrayList<>(); // Zapisywanie krawędzi

    for (int u = 0; u < NUMBER_OF_NODES; u++) {
      for (int k = 0; k < 9; k++) {
        char[] node = getNode(u); // Pobieranie węzła odpowiadającego wierzchołkowi u
        if (node[k] == 'O') {
          int v = getFlippedNode(node, k);
          // Dodawanie krawędzi (v, u), jeśli istnieje ruch powodujący przejście od węzła u do węzła v
          edges.add(new 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) { 
      // W granicach macierzy
      if (node[row * 3 + column] == 'O')
        node[row * 3 + column] = 'R'; // Zmiana z O na R
      else
        node[row * 3 + column] = 'O'; // Zmiana z R na O
    }
  }

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

    for (int i = 0; i < 9; i++)
      if (node[i] == 'R')
        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] = 'O';
      else
        result[8 - i] = 'R';
      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();
  }
}
