51. N-Queens

2018年4月13日 下午3:54

N-Queens - LeetCode

1. 这道题很多细节没有考虑到，导致做出来总是报执行异常。
   1. 以后碰见异常问题、出错问题时要先检查字母是否写错了、循环的边界多多少少、条件判断顺序、or\and
2. 为啥这道题中要以每一行为一个generate()的遍历对象，而不是以每一个行为一个元素？
   1. 要说明白这个问题就需要理解递归其实是可以让程序并行执行的。
   2. 那么，什么是并行，怎样判断并行的元素？？
      1. 78. Subsets先看一下这个对递归的总结。
      2. 在这道题中，我们需要的是在每行的各个元素中，找到每次找到一个可以满足N-Queens的元素。在这一行中可能有很多元素都满足，但是要求，在每次测试某个元素的时候，不能被上一个元素所影响，这就是所说的其他元素要恢复原状。
      3. 总结一下：并行，一般都需要在不同的元素之间进行相同的动作，但是在操作不同的元素的时候，我们是不可以受其他元素的影响，一般的方法就是要将其他元素操作完之后恢复原状。
   3. 我们需要并行的元素是一行的中的各个元素，那么我们就需要将一行作为一个函数，也就是这里的generate的操作对象。

class Solution {
public:
    std::vector<std::vector<std::string>> solveNQueens(int n) {
        std::vector<std::vector<int>> mark;
        std::vector<std::string> location;
        std::vector<std::vector<std::string>> result;

        //初始化mark location
        for(int i = 0; i < n; i++){
            mark.push_back((std::vector<int>() ));//初始化二维数组
            for(int j = 0; j < n; j++){

                mark[i].push_back(0);
            }
            location.push_back("");//初始化的方法
            location[i].append(n, '.');
        }

        generate(0, n, mark, location, result);

        return result;
    }
private:
    void put_down_the_queen(int x, int y, std::vector<std::vector<int>> &mark){
        static const int dx[] = {-1,1,0,0,-1,-1,1,1};
        static const int dy[] = {0,0,-1,1,-1,1,-1,1};

        mark[x][y] = 1;//不要忘了
        for(int i = 0; i < 8 ; i++){
            for(int j = 1; j < mark.size() ; j++){//最多是N-1,不是n，所以j <= mark.size()是错的
                int a = x+j*dx[i];
                int b = y+j*dy[i];
                             
                if(a < 0 || a >= mark.size() || b < 0 || b > mark.size()){//这里是or。错把a,写成b。找了一个小时
                    break;
                }
                mark[a][b] = 1;
            }
        }
    }

    void generate(int i,int n, std::vector<std::vector<int>> &mark,
                  std::vector<std::string> &location,
                  std::vector<std::vector<std::string>> &result){
        if(i == n){
            result.push_back(location);
            return;
        }
        //遍历一行中的每个位置，如果不冲突，那么put_down_the_queen,下一行
        for(int j = 0; j < n; j++){
            if(mark[i][j]==0){
                std::vector<std::vector<int>> temp_mark = mark;
                //放置皇后，接着递归
                put_down_the_queen(i, j, mark);
                location[i][j] = 'Q';
                generate(i+1, n, mark, location,result);

                //恢复
                location[i][j] = '.';
                mark = temp_mark;
            }

        }
    }

};