package com.yangli907.LNKN;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Given a chessboard represented by 2D array, there's a knight at (0, 0) position.
 * Count how many different ways can the knight moved to (n-1, n-1) position in EXACTLY k steps.
 * There's NO restriction on how many times knight can move to same cell in the board.
 *
 * i.e. given a 4x4 board with k = 2, then the answer is 2.
 *
 * Optionally print out the satisfied path.
 */
public class KnightMoveKSteps {

    public static void main(String[] args) {
        int[][] M = new int[4][4];
        int[] s = {0, 0};
        int[] e = {3, 3};
        int k = 3;
        int ways = new KnightMoveKSteps().countWays(M, s, e, k);

        System.out.println(ways);
    }

    /**
     * BFS, with a queue to store the next possible moves.
     * Use DP[k][i][j] to store the answer for ways to reach cell (i, j) at step k.
     */
    private int countWays(int[][] M, int[] s, int[] e, int k) {

        int row = M.length;
        int col = M[0].length;

        int[][][] dp = new int[k + 1][row][col];
        dp[0][s[0]][s[1]] = 1;

        Queue<int[]> q = new LinkedList<>();
        q.add(s);
        Queue<List<String>> paths = new LinkedList<>();
        paths.add(Arrays.asList("(0, 0)"));

        for(int i = 0; i < k; i++) {

            int[] dx = {1, 1, -1, -1, 2, 2, -2, -2};
            int[] dy = {2, -2, 2, -2, 1, -1, 1, -1};
            int size = q.size();

            for(int j = 0; j < size; j++) {
                int[] cur = q.remove();
                List<String> path = paths.remove();

                for(int d = 0; d < 8; d++) {
                    int xx = cur[0] + dx[d];
                    int yy = cur[1] + dy[d];

                    if (isValid(M, xx, yy)) {
                        dp[i+1][xx][yy] += dp[i][cur[0]][cur[1]];
                        int[] next = {xx, yy};
                        q.add(next);
                        List<String> copy = new ArrayList<>(path);
                        copy.add("(" + xx + ", " + yy + ")");
                        paths.add(copy);

                        if (next[0] == e[0] && next[1] == e[1] && i == k - 1) {
                            System.out.println(copy.toString());
                        }
                    }
                }
            }

        }

        for(int i = 0; i < M.length; i++) {
            for(int j = 0; j < dp[0].length; j++) {
                System.out.print(dp[k][i][j] + "\t");
            }
            System.out.println();
        }

        return dp[k][row - 1][col - 1];
    }

    private boolean isValid(int[][] M, int x, int y) {
        return x >= 0 && y >= 0 && x < M.length && y < M[0].length;
    }
}