52. N-Queens II.txt

//Ýòà çàäà÷à íè÷åì íå îòëè÷àåòñÿ îò ïðåäûäóùåé. Ïðîñòî âìåñòî âåêòîðà ans âîçâðàùàåì åãî ðàçìåð ans.size().

class Solution {
public:
    void solve(int col, int n, vector<vector<string>>&ans, vector<string>&board, vector<int>&leftrow, vector<int>&upperDiagonal, vector<int>&lowerDiagonal) {
        if (col == n) {//Óñëîâèå âûõîäà èç ðåêóðñèè
            ans.push_back(board);//äîáàâëÿåì âðåìåííûé âåêòîð â âåêòîð ôèíàëüíîãî îòâåòà.
            return;
        }
        for (int row = 0; row < n; row++) {//Öèêë ïî âñåì ýëåìåíòàì ñòðîêè
            //Åñëè òåêóùèé ýëåìåíò ñòðîêè == 0 È 
            if (leftrow[row] == 0 && lowerDiagonal[row + col] == 0 && upperDiagonal[n - 1 + col - row] == 0) {
                board[row][col] = 'Q';//Ïðèñâàèâàåì òåêóùåìó ýëåìåíòó ñòðîêè çíà÷åíèå Q.
                leftrow[row] = 1;//Ñîõðàíÿåì çàïèñü â êàêîé ñòðîêå ïîñòàâëåíà Q
                lowerDiagonal[row + col] = 1;//Ñîõðàíÿåì êýø íèæíåé äèàãîíàëè
                upperDiagonal[n - 1 + col - row] = 1;//Ñîõðàíÿåì êýø âåðõíåé äèàãîíàëè
                solve(col + 1, n, ans, board, leftrow, upperDiagonal, lowerDiagonal);//Âûçûâàåì ðåêóðñèþ.
                board[row][col] = '.';//Ìåíÿåì îáðàòíî ñ Q íà òî÷êó
                leftrow[row] = 0;//Îáíóëÿåì õåø ñòðîêè
                lowerDiagonal[row + col] = 0;//Îáíóëÿåì õåø íèæíåé äèàãîíàëè
                upperDiagonal[n - 1 + col - row] = 0;//Îáíóëÿåì õåø âåðõíåé äèàãîíàëè
            }
        }
    }
    int totalNQueens(int n) {
        vector<vector<string>> ans;//Ñîçäà¸ì âåêòîð ôèíàëüíîãî îòâåòà
        vector<string> board(n);//Âåêòîð âðåìåííîãî îòâåòà
        string s(n, '.');//Çàïîëíÿåì ñòðîêó n-íûì êîë-âîì òî÷åê
        for (int i = 0; i < n; i++) {//Äîáàâëÿåì ñòðîêè â âåêòîð âðåìåííîãî îòâåòà
            board[i] = s;
        }
        //Ñîçäà¸ì âñïîìîãàòåëüíûå âåêòîðà 
        vector<int>leftrow(n, 0), upperDiagonal((2 * n) - 1, 0), lowerDiagonal((2 * n) - 1, 0);
        solve(0, n, ans, board, leftrow, upperDiagonal, lowerDiagonal);//Âûçûâàåì ôóíêöèþ ðåêóðñèè
        return ans.size();
    }
};