注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
本帖最后由 oio14644 于 2015-9-6 14:05 编辑
II 在1的基础上微调即可,红色字体部分
I
ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
ArrayList<ArrayList<String>> solveNQueens(int n) {
helper(new int[n][n], 0);
return res;
}
private void helper(int[][] board, int row) {
if (row == board.length) {
ArrayList<String> list = new ArrayList<String>();
for (int i = 0; i < board.length; i++) {
String s = "";
for (int j = 0; j < board.length; j++) {
if (board[j] == 1) {
s += "Q";
} else {
s += ".";
}
}
list.add(s);
}
res.add(list);
return;
}
for (int col = 0; col < board.length; col++) {
board[row][col] = 1;
if (!isValid(board, row, col)) {
board[row][col] = 0;
continue;
} else {
helper(board, row + 1);
board[row][col] = 0;
}
}
}
private boolean isValid(int[][] board, int row, int col) {
for (int i = 0; i < row; i++) {
if (board[i][col] == 1) {
return false;
}
if (col - row + i >= 0 && board[i][col - row + i] == 1) {
return false;
}
if (col + row - i < board.length && board[i][col + row - i] == 1) {
return false;
}
}
return true;
}
===========================================================================================================================
II
private int sum = 0;
public int totalNQueens(int n) {
helper(new int[n][n], 0);
return sum;
}
private void helper(int[][] board, int row) {
if (row == board.length) {
sum++;
return;
}
for (int col = 0; col < board.length; col++) {
board[row][col] = 1;
if (!isValid(board, row, col)) {
board[row][col] = 0;
continue;
} else {
helper(board, row + 1);
board[row][col] = 0;
}
}
}
private boolean isValid(int[][] board, int row, int col) {
for (int i = 0; i < row; i++) {
if (board[i][col] == 1) {
return false;
}
if (col - row + i >= 0 && board[i][col - row + i] == 1) {
return false;
}
if (col + row - i < board.length && board[i][col + row - i] == 1) {
return false;
}
}
return true;
}
[/i][/i][/i][/i][/i][/i] |