LeetCode: N-Queens

题目

https://oj.leetcode.com/problems/n-queens/

分析

  1. 这道题采用的是回溯法,跟DFS非常类似,只不过是在DFS的递归前加一个判断。

  2. 关于如何表示结果。

可以采用一个N*N二维数组来存放结果,但是我们可以采用更好的办法:经过观察我们可以发现,每一行必然有一个皇后,因此我们可以用一个一维数组来表示结果,solution[0]=3 代表第0行的皇后放在第三列, solution[1]=5 代表第1行的皇后放在第5列,……以此类推。

  1. 关于如何判断一种结果是否合法。

题目要求任意两个皇后不能在同一行、同一列或者用一斜线上,在2中我们已经提过了用一维数组solution[n]来表示结果,任两个皇后肯定不在同一行,判断第i行和第j行的皇后是否同一列可以用 solution[i] == solution[j]来判断;如何判断第i行皇后和第j行皇后是否在同一斜线上呢?可以用 abs(i-j) == abs(solution[i] - solution[j]) 来判断。

代码

class Solution
{
public:
    vector<vector<string>> solveNQueens(int n)
    {
        vector<int> solution(n);
        helper(solution, 0, n);

        return res;
    }

    void helper(vector<int>& solution, int row, int n)
    {
        if (row == n)
        {
            vector<string> solution_2d(n, string(n, '.'));
            for (int i = 0; i < n; i++)
                solution_2d[i][solution[i]] = 'Q';

            res.push_back(solution_2d);
        }
        else
        {
            for (int i = 0; i < n; i++)
            {
                if (isValid(solution, row, i))
                {
                    solution[row] = i;
                    helper(solution, row + 1, n);
                }
            }
        }
    }

    bool isValid(vector<int>& solution, int row, int col)
    {
        for (int i = 0; i < row; i++)
            if (solution[i] == col || abs(i-row) == abs(solution[i]-col))
                return false;
        return true;
    }

private:
    vector<vector<string>> res;
};

参考

http://www.cnblogs.com/TenosDoIt/p/3801621.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40686105