算法随想Day27【回溯算法】| LC332-重新安排行程、LC51-N皇后、LC37-解数独

LC332. 重新安排行程

做了很久，还是没有通过全部案例，最后是一个输入为100个元素的数组，运行超出时间限制。

LC51. N皇后

实现了回溯算法中的超暴力解法，主要是对某个节点的斜线，在用数学式去表示的思想没想到。

官方解法：

auto columns = unordered_set(); //即相当于我的y_uset，x_uset其实可以不用，因为在传参时的int x中已经暗含，不会出现重复
auto diagonals1 = unordered_set();
auto diagonals2 = unordered_set();

diagonal表示对某个坐标的两条斜线，分别记录x - y的值 和 y - x的值，如此时(x, y) = (2, 4)，则其两条斜线上的每个坐标分别会满足表达式x - y = -3, x + y = 6；

其实对x_y_uset只存放为unordered_set，如对

vector<vector<string>> result;
unordered_set<int> x_uset;
unordered_set<int> y_uset;
map<pair<int, int>, int> x_y_uset;
void NQueensLoop(int& n, vector<string>& temp, int x)
{
    if (x >= n)
    {
        result.emplace_back(temp);
        return;
    }
    for (int y = 0; y < n; ++y)
    {
        if (x_uset.find(x) != x_uset.end() || y_uset.find(y) != y_uset.end())
            continue;
        if (x_y_uset.find(pair<int, int>{x, y}) != x_y_uset.end())
            continue;
        temp[x][y] = 'Q';
        x_uset.emplace(x);
        y_uset.emplace(y);
        x_y_uset[pair<int, int>{x, y}] = 1;
        //x_y_uset.emplace(pair<int, int>{x, y});
        for (int temp_x = x + 1, temp_y = y + 1; temp_x >= 0 && temp_x < n && temp_y >= 0 && temp_y < n; ++temp_x, ++temp_y)
        {
            if (x_y_uset.find(pair<int, int>{temp_x, temp_y}) == x_y_uset.end())
                x_y_uset[pair<int, int>{temp_x, temp_y}] = 1;
            else
                x_y_uset[pair<int, int>{temp_x, temp_y}]++;      
        }
        for (int temp_x = x - 1, temp_y = y - 1; temp_x >= 0 && temp_x < n && temp_y >= 0 && temp_y < n; --temp_x, --temp_y)
        {
            if (x_y_uset.find(pair<int, int>{temp_x, temp_y}) == x_y_uset.end())
                x_y_uset[pair<int, int>{temp_x, temp_y}] = 1;
            else
                x_y_uset[pair<int, int>{temp_x, temp_y}]++; 
        }
        for (int temp_x = x + 1, temp_y = y - 1; temp_x >= 0 && temp_x < n && temp_y >= 0 && temp_y < n; ++temp_x, --temp_y)
        {
            if (x_y_uset.find(pair<int, int>{temp_x, temp_y}) == x_y_uset.end())
                x_y_uset[pair<int, int>{temp_x, temp_y}] = 1;
            else
                x_y_uset[pair<int, int>{temp_x, temp_y}]++; 
        }
        for (int temp_x = x - 1, temp_y = y + 1; temp_x >= 0 && temp_x < n && temp_y >= 0 && temp_y < n; --temp_x, ++temp_y)
        {
            if (x_y_uset.find(pair<int, int>{temp_x, temp_y}) == x_y_uset.end())
                x_y_uset[pair<int, int>{temp_x, temp_y}] = 1;
            else
                x_y_uset[pair<int, int>{temp_x, temp_y}]++; 
        }
        NQueensLoop(n, temp, x + 1);
        temp[x][y] = '.';
        x_uset.erase(x);
        y_uset.erase(y);
        x_y_uset.erase(pair<int, int>{x, y});
        for (int temp_x = x + 1, temp_y = y + 1; temp_x >= 0 && temp_x < n && temp_y >= 0 && temp_y < n; ++temp_x, ++temp_y)
        {
            if (x_y_uset.find(pair<int, int>{temp_x, temp_y}) != x_y_uset.end())
            {
                x_y_uset[pair<int, int>{temp_x, temp_y}]--;
                if (x_y_uset[pair<int, int>{temp_x, temp_y}] == 0)
                    x_y_uset.erase(pair<int, int>{temp_x, temp_y});
            }
        }
        for (int temp_x = x - 1, temp_y = y - 1; temp_x >= 0 && temp_x < n && temp_y >= 0 && temp_y < n; --temp_x, --temp_y)
        {
            if (x_y_uset.find(pair<int, int>{temp_x, temp_y}) != x_y_uset.end())
            {
                x_y_uset[pair<int, int>{temp_x, temp_y}]--;
                if (x_y_uset[pair<int, int>{temp_x, temp_y}] == 0)
                    x_y_uset.erase(pair<int, int>{temp_x, temp_y});
            }
        }
        for (int temp_x = x + 1, temp_y = y - 1; temp_x >= 0 && temp_x < n && temp_y >= 0 && temp_y < n; ++temp_x, --temp_y)
        {
            if (x_y_uset.find(pair<int, int>{temp_x, temp_y}) != x_y_uset.end())
            {
                x_y_uset[pair<int, int>{temp_x, temp_y}]--;
                if (x_y_uset[pair<int, int>{temp_x, temp_y}] == 0)
                    x_y_uset.erase(pair<int, int>{temp_x, temp_y});
            }
        }
        for (int temp_x = x - 1, temp_y = y + 1; temp_x >= 0 && temp_x < n && temp_y >= 0 && temp_y < n; --temp_x, ++temp_y)
        {
            if (x_y_uset.find(pair<int, int>{temp_x, temp_y}) != x_y_uset.end())
            {
                x_y_uset[pair<int, int>{temp_x, temp_y}]--;
                if (x_y_uset[pair<int, int>{temp_x, temp_y}] == 0)
                    x_y_uset.erase(pair<int, int>{temp_x, temp_y});
            }
        }
    }
}
vector<vector<string>> solveNQueens(int n)
{
    vector<string> temp(n, string(n, '.'));
    NQueensLoop(n, temp, 0);
    return result;
}

LC37. 解数独

最暴力的回溯解法

typedef vector<unordered_set<char>> REC;

class Solution
{
/*
    —— —— → y
    |
    |
    ↓ x
*/
public:
    vector<vector<char>> result;
    void SudokuLoop(vector<vector<char>>& board, REC& x, REC& y, REC& nine, int row, int column)
    {
        while(board[row][column] != '.')
        {
            ++column;
            if (column > 8)
            {
                column = 0;
                ++row;
            }
            if (row > 8)
            {
                result = board;
                return;
            }
        }

        int index = (row / 3) * 3 + column / 3;
        for (char i = '1'; i <= '9'; ++i)
        {
            if (x[row].find(i) != x[row].end() || y[column].find(i) != y[column].end() || nine[index].find(i) != nine[index].end())
            {
                continue;
            }
            board[row][column] = i;
            x[row].emplace(i);
            y[column].emplace(i);
            nine[index].emplace(i);
            SudokuLoop(board, x, y, nine, row, column + 1);
            board[row][column] = '.';
            x[row].erase(i);
            y[column].erase(i);
            nine[index].erase(i);
        }        
    }
    void solveSudoku(vector<vector<char>>& board)
    {
        REC nine(9);
        REC x;
        REC y;
        unordered_set<char> temp;
        for (int i = 0; i < 9; ++i)
        {
            for (int j = 0; j < 9; ++j)
            {
                if (board[i][j] != '.')
                {
                    temp.emplace(board[i][j]);
                }
            }
            x.emplace_back(temp);
            temp.clear();
            for (int j = 0; j < 9; ++j)
            {
                if (board[j][i] != '.')
                {
                    temp.emplace(board[j][i]);
                }
            }
            y.emplace_back(temp);
            temp.clear();

            for (int j = 0; j < 9; ++j)
            {
                int index = (i / 3) * 3 + j / 3;
                if (board[i][j] != '.')
                {
                    nine[index].emplace(board[i][j]);
                }
            }  
        }
        SudokuLoop(board,x, y, nine, 0, 0);
        board = result;
    }
};