hacktoberfest21/Leetcode51.cpp at main · bakiyaswanth/hacktoberfest21 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:

    vector<vector<string>> ans;
     bool isItSafeToPlace(vector<vector<int>> &arr,int row,int col)
        {
            for (int curRow= row-1; curRow>=0; curRow--)
            {
                if (arr[curRow][col]==1) return false;
            }

            for (int curRow= row-1, curCol= col-1; curRow>=0 && curCol>=0; curRow--,curCol--)
            {
                if (arr[curRow][curCol]==1) return false;
            }

            for (int curRow= row-1, curCol= col+1; curRow>=0 && curCol<arr.size(); curRow--,curCol++)
            {
                if (arr[curRow][curCol]==1) return false;
            }

         return true;
     }


    void nQueens(vector<vector<int>> &board,int row)
    {
        if(row==board.size())
        {

            vector<string> curAns;

            for(int indr=0;indr<board.size();indr++)
            {
                string str="";

                for(int indc=0;indc<board[0].size();indc++)
                {

                    if(board[indr][indc]==0)
                        str+=".";
                    else
                        str+="Q";
                }

                curAns.push_back(str);
            }

            ans.push_back(curAns);

            return;
        }

        for(int curCol=0;curCol<board.size();curCol++)
        {
            if(isItSafeToPlace(board,row,curCol))
            {

                board[row][curCol]=1;

                nQueens(board,row+1);


            }


                board[row][curCol]=0;
        }


    vector<vector<string>> solveNQueens(int n){


        vector<vector<int>> board;

        for(int ind=0;ind<n;ind++)
        {
            vector<int> temp;

            for(int indj=0;indj<n;indj++)
            {
                temp.push_back(0);
            }

            board.push_back(temp);
        }


        nQueens(board,0);

        return ans;
    }


};