一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 194|回复: 0
收起左侧

[二分/排序/搜索] NQueens I II

[复制链接] |试试Instant~ |关注本帖
oio14644 发表于 2015-9-6 14:02:31 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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[col] == 1) {
                                return false;
                        }
                        if (col - row + i >= 0 && board[col - row + i] == 1) {
                                return false;
                        }
                        if (col + row - i < board.length && board[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[col] == 1) {
                                return false;
                        }
                        if (col - row + i >= 0 && board[col - row + i] == 1) {
                                return false;
                        }
                        if (col + row - i < board.length && board[col + row - i] == 1) {
                                return false;
                        }
                }
                return true;
        }

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 08:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表