The most intuitive way is to rotate the board


#1

This allows you to split up the problem in one horizontal/vertical problem and one diagonal problem. All directions can be created by just rotating the board 4 times :slight_smile: . This is still DP, but instead split up.

The editorial solution seems really unreadable.

Code is below:

public class Solution {

public ArrayList<ArrayList<Integer>> queenAttack(ArrayList<String> input) {
    int[][] board = parse(input);
    if (input.size() == 0 || input.get(0).length() == 0) {
        return asArrayList(board);
    }
    int[][] acc = emptyClone(board);
    /*
     * calculate:
     *  - queenAttackRight, queenAttackUpRight
     *  - queenAttackUp, queenAttackUpLeft
     *  - queenAttackLeft, queenAttackDownLeft
     *  - queenAttackDown, queenAttackDownRight
     */
    int[][] previousBoard = null;
    int[][] previousAcc = null;
    int[][] swap = null;
    int[][] scratchPad = emptyClone(board);
    int[][] scratchPadNext = rotateCW(scratchPad, null);
    for (int rot = 0; rot < 4; rot++) {
        queenAttackRight(acc, scratchPad, board);
        queenAttackUpRight(acc, scratchPad, board);
        // rotate our board to get next directions
        swap = board;
        board = rotateCW(board, previousBoard);
        previousBoard = swap;
        swap = acc;
        acc = rotateCW(acc, previousAcc);
        previousAcc = swap;
        // 'rotate' the scratchpad
        swap = scratchPad;
        scratchPad = scratchPadNext;
        scratchPadNext = swap;
    }
    return asArrayList(acc);
}

public void queenAttackRight(int[][] acc,
    int[][] scratchPad,
    int[][] board) {
    int N = board.length;
    int M = board[0].length;
    for (int i = 0; i < N; i++) {
        // helper variables
        int[] boardRow = board[i];
        int[] scratchRow = scratchPad[i];
        int[] accRow = acc[i];
        // actual logic:
        for (int j = 0; j < M; j++) {
            if (j == 0) {
                scratchRow[j] = 0;
                // no one can attack from the right if we are on the left border
                continue;
            }
            int queens = scratchRow[j - 1];
            if (boardRow[j - 1] != 0) {
                // queen is blocking all other queens + this queen can attack here
                queens = 1;
            }
            scratchRow[j] = queens;
            accRow[j] += queens;
        }
    }
}

public void queenAttackUpRight(int[][] acc,
    int[][] scratchPad,
    int[][] board) {
    int N = board.length;
    int M = board[0].length;
    for (int i = N - 1; i >= 0; i--) {
        // helper variables
        int[] boardRow = board[i];
        int[] boardNextRow = i == N - 1 ? null : board[i + 1];
        int[] scratchRow = scratchPad[i];
        int[] scratchNextRow = i == N - 1 ? null : scratchPad[i + 1];
        int[] accRow = acc[i];
        // actual logic:
        for (int j = 0; j < N; j++) {
            if (i == N - 1 || j == 0) {
                scratchRow[j] = 0;
                // no one can attack you if you are on the bottom of the left border
                continue;
            }
            int queens = scratchNextRow[j - 1];
            if (boardNextRow[j - 1] != 0) {
                // queen is blocking all other queens + this queen can attack here
                queens = 1;
            }
            scratchRow[j] = queens;
            accRow[j] += queens;
        }
    }
}

private int[][] parse(ArrayList<String> input) {
    int[][] output = new int[input.size()][];
    for (int i = 0; i < input.size(); i++) {
        String row = input.get(i);
        int[] outputRow = new int[row.length()];
        output[i] = outputRow;
        int j = 0;
        for (char c : row.toCharArray()) {
            output[i][j++] = (c == '1' ? 1 : 0);
        }
    }
    return output;
}

/*  0 1 0      010
 *  1 0 0   => 001
 *  0 0 1      100
 */
private int[][] rotateCW(int[][] board,
    int[][] output) {
    int N = board.length;
    int M = board[0].length;
    boolean outputProvided = output != null;
    if (outputProvided) {
        for (int i = 0; i < M; i++) {
            int[] outputRow = output[i];
            for (int j = 0; j < N; j++) {
                outputRow[j] = board[N - j - 1][i];
            }
        }
        return output;
    }
    output = new int[board.length][];
    for (int i = 0; i < M; i++) {
        int[] outputRow = new int[board[i].length];
        for (int j = 0; j < N; j++) {
            outputRow[j] = board[N - j - 1][i];
        }
        output[i] = outputRow;
    }
    return output;
}

private int[][] emptyClone(int[][] board) {
    int[][] result = new int[board.length][];
    int N = board.length;
    int M = board[0].length;
    for (int i = 0; i < N; i++) {
        result[i] = new int[M];
    }
    return result;
}

private ArrayList<ArrayList<Integer>> asArrayList(int[][] board) {
    ArrayList<ArrayList<Integer>> output = new ArrayList<>();
    for (int[] boardRow : board) {
        ArrayList<Integer> outputRow = new ArrayList<>();
        for (int i : boardRow) {
            outputRow.add(i);
        }
        output.add(outputRow);
    }
    return output;
}

private int[][] output(int[][] board) {
    for (int i : board[0]) {
        System.out.print("--");
    }
    System.out.println();
    for (int[] row : board) {
        for (int i : row) {
            System.out.print(i);
            System.out.print(' ');
        }
        System.out.println();
    }
    for (int i : board[0]) {
        System.out.print("--");
    }
    System.out.println();
    System.out.println();
    return board;
}

}