import java.util.Stack;

public class PegAI {
    public static void main(String[] args) {
        int  b[][]={{2,2,0,1,0,2,2},
                {2,2,1,1,1,2,2},
                {0,1,1,1,1,1,0},
                {1,1,1,0,1,1,1},
                {0,1,1,1,1,1,0},
                {2,2,1,1,1,2,2},
                {2,2,0,1,0,2,2}};

        PegAI pegAI = new PegAI(b);
        pegAI.Search();
        Stack way  = new Stack();
        
        //從closedStack中取出 拔釘子 的路徑放入 way 中
        System.out.println();
        System.out.println("closedStack大小："+pegAI.closedStack.size());
        while(!pegAI.closedStack.empty()){
            OnePeg wayPeg = (OnePeg) pegAI.closedStack.pop();
            way.push( wayPeg );

        }
        
        
        //輸出 拔釘子 的全部路徑
        System.out.println("way大小："+way.size());
        int i=1;
        while(!way.empty()){
            OnePeg wayPeg = (OnePeg) way.pop();
            System.out.println("第"+i+"步："+ (wayPeg.getX()-1) +" "
                    + (wayPeg.getY()-1 )+" " +wayPeg.getDir());
            i++;
        }
        
            

    }

    public PegAI(int input[][]) {
        // 初始化 棋盤,第0行，第8行，第1列，第8列元素都是2，其他是輸入矩陣
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (i == 0 || i == 8 || j == 0 || j == 8)
                    board[i][j] = 2; // 設置一個圍墻
                else {
                    board[i][j] = input[i - 1][j - 1];
                    if (board[i][j] == 1)
                        count++;
                }
        
        sum = count;
        son = new int[sum-1];
        tryMove();
        
    }

    public void Search() {
        //打印初始棋盤
        System.out.println("初始棋盤如下：");
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
        
        System.out.println("一開始，釘子個數" + count);
        System.out.println();
        System.out.println();
        
        long begin = System.currentTimeMillis();
        while (count > 1) {
            times++;

            if (!openStack.empty()) {// openStack非空
                // 把openStack的 棧頂節點 取出放入 closedStack
                OnePeg peg = (OnePeg) openStack.pop();
                count--;
                closedStack.push(peg);

                // 下棋
                switch (peg.getDir()) {
                case 'U':
                    moveUp(peg.getX(), peg.getY());
                    break;
                case 'D':
                    moveDown(peg.getX(), peg.getY());
                    break;
                case 'L':
                    moveLeft(peg.getX(), peg.getY());
                    break;
                case 'R':
                    moveRight(peg.getX(), peg.getY());
                    break;
                }

                if (count > 1 && !tryMove()) { // 釘子剩下不只一個，而且是 死棋，考慮回溯
                    recollection(peg);
                    closedStack.pop(); // closedStack棧頂元素退棧

                    while (father > -1 && son[father] == 0) { // 本層擴展已經全部結束，則其父親節點也不可擴展，將其退棧，并回溯
                        father--;
                        OnePeg Peg = (OnePeg) closedStack.pop();
                        recollection(Peg);
                    }
                }

            } else
                System.out.println("問題無解 - -!");

        }
        long end = System.currentTimeMillis();
        System.out.println("耗時：" + (end - begin) + "毫秒");
        System.out.println("恭喜，闖關成功!!!");
        System.out.println("closedStack中有" + closedStack.size() + "釘子");
        System.out.println("總共走了" + times + "步");

        
        // 打印棋盤
        System.out.println("經過DFS,游戲通關了：");
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("結束時，釘子個數" + count);

    }

    // 回溯
    public void recollection(OnePeg peg) {

        if (son[father] > 0) {

            son[father]--;

        }
        count++;

        char dir = peg.getDir();
        int x = peg.getX();
        int y = peg.getY();
        switch (dir) {
        case 'U':
            board[x][y] = 1;
            board[x - 1][y] = 1;
            board[x - 2][y] = 0;
            break;
        case 'D':
            board[x][y] = 1;
            board[x + 1][y] = 1;
            board[x + 2][y] = 0;
            break;
        case 'L':
            board[x][y] = 1;
            board[x][y - 1] = 1;
            board[x][y - 2] = 0;
            break;
        case 'R':
            board[x][y] = 1;
            board[x][y + 1] = 1;
            board[x][y + 2] = 0;
            break;
        }

    }

    // 判斷 并移動和記錄
    public boolean tryMove() {
        int sum = 0;
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == 1)
                    sum += moveAndPush(i, j);
            }
        if (sum > 0) {
            // if(son[father])
            father++; // 此處需要修改
            son[father] = sum;
            return true;
        } else
            return false;
    }

    // 移動和記錄
    public int moveAndPush(int x, int y) {
        int sum = 0;
        if (up(x, y)) {
            openStack.push(new OnePeg(x, y, 'U'));
            sum++;
        }
        if (down(x, y)) {
            openStack.push(new OnePeg(x, y, 'D'));
            sum++;
        }
        if (left(x, y)) {
            openStack.push(new OnePeg(x, y, 'L'));
            sum++;
        }
        if (right(x, y)) {
            openStack.push(new OnePeg(x, y, 'R'));
            sum++;
        }
        return sum;
    }

    // 向上跳
    private void moveUp(int x, int y) {
        board[x][y] = 0;
        board[x - 1][y] = 0;
        board[x - 2][y] = 1;
    }

    // 向下跳
    private void moveDown(int x, int y) {
        board[x][y] = 0;
        board[x + 1][y] = 0;
        board[x + 2][y] = 1;
    }

    // 向左跳
    private void moveLeft(int x, int y) {
        board[x][y] = 0;
        board[x][y - 1] = 0;
        board[x][y - 2] = 1;
    }

    // 向右跳
    private void moveRight(int x, int y) {
        board[x][y] = 0;
        board[x][y + 1] = 0;
        board[x][y + 2] = 1;
    }

    // 判斷向上走的可能性
    private boolean up(int i, int j) {
        if (i > 2 && i < 8 && board[i - 1][j] == 1 && board[i - 2][j] == 0)
            return true;
        else
            return false;
    }

    // 判斷向下走的可能性
    private boolean down(int i, int j) {
        if (i < 6 && i > 0 && board[i + 1][j] == 1 && board[i + 2][j] == 0)
            return true;
        else
            return false;
    }

    // 判斷向左走的可能性
    private boolean left(int i, int j) {
        if (j > 2 && j < 8 && board[i][j - 1] == 1 && board[i][j - 2] == 0)
            return true;
        else
            return false;
    }

    // 判斷向右走的可能性
    private boolean right(int i, int j) {
        if (j < 6 && j > 0 && board[i][j + 1] == 1 && board[i][j + 2] == 0)
            return true;
        else
            return false;
    }

    private int sum = 0;

    private int[] son = null;

    private int father = -1;

    private int times = 0;

    private Stack openStack = new Stack();

    private Stack closedStack = new Stack();

    private int count = 0;

    private int[][] board = new int[9][9];
}