搜索

DFS

优缺点：

• 容易爆栈，如果有1e4层就爆了。
• 空间和深度成正比，相对较小
• 不能搜最短、最小

排列数字

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

#include <iostream>
#include <vector>

using namespace std;

int n;
int use[10] = {0};

void dfs(vector<int> res)
{
    if(res.size()==n)
    {
        for(int i = 0; i < n; i ++)
            cout << res[i] <<" ";
        cout << endl;
        return;
    }
    for(int i = 1; i <= n; i ++)
        if(!use[i])
        {
            use[i] = 1;
            res.push_back(i);
            dfs(res);
            res.pop_back();
            use[i] = 0;
        }
}

int main()
{
    vector<int> res;
    cin >> n;
    dfs(res);
}

n-皇后问题

n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入样例：
4
输出样例：
.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

#include<iostream>

using namespace std;

const int N = 20;
char map[N][N];
// 标记该点对应的列、斜线、反斜线是否有皇后，从左下到右上对应slash[1~15]，从左上到右下对应backslash[1~15]
bool col[N], slash[N*2], backslash[N*2]; 
int n;

void dfs(int row)
{
    if(row == n + 1)
    {
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 1; j <= n; j ++)
                cout << map[i][j];
            cout << endl;
        }
        cout << endl;
    }
    for(int j = 1; j <= n; j ++)
    {
        if(!col[j] && !slash[j - row + n] && !backslash[j + row -1])
        {
            map[row][j] = 'Q';
            col[j] = slash[j - row + n] = backslash[j + row - 1] = true;
            dfs(row + 1);
            map[row][j] = '.';
            col[j] = slash[j - row + n] = backslash[j + row - 1] = false;
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            map[i][j] = '.';
    dfs(1);
    return 0;
}

BFS

优缺点：

• 空间的指数级别大
• 不会有爆栈的风险
• 可以搜最短、最小

走迷宫

给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。

数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int n, m;
    bool map[101][101];
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    int dis[101][101];
    queue<pair<int, int> > q;
    
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j++)
        {
            cin >> map[i][j];
            dis[i][j] = -1;
        }
    dis[1][1] = 0;
    q.push({1, 1});
    
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if(nextx>=1 && nextx<=n && nexty>=1 && nexty<=m && map[nextx][nexty]==0 && dis[nextx][nexty] == -1)
            {
                q.push({nextx, nexty});
                dis[nextx][nexty] = dis[x][y] + 1;
            }
        }
    }
    cout << dis[n][m];
    return 0;
}

数字华容道

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

int main()
{
    string start;
    string tmp;
    queue<string> q;
    unordered_map<string, int> d;
    
    string ans = "12345678x";
    
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
    
    for(int i = 0; i < 9; i ++)
    {
        cin >> tmp;
        start += tmp;
    }
    
    // cout << start << endl;
    
    q.push(start);
    d[start] = 0;
    
    
    while(!q.empty())
    {
        string str = q.front();
        q.pop();
        int dis = d[str];
        
        int k = str.find('x');
        int x = k / 3, y = k % 3;
        
        for(int i = 0; i < 4; i ++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 0 && nx < 3 && ny >= 0 && ny < 3)
            {
                swap(str[nx * 3 + ny], str[k]);
                if(str == ans) 
                {
                    cout << dis + 1 << endl;
                    return 0;
                }
                
                if(d.find(str) == d.end())
                {
                    q.push(str);
                    d[str] = dis + 1;
                }
                    
                swap(str[nx * 3 + ny], str[k]);
            }
            
        }
        
    }
    cout << -1 <<endl;
    return 0;
    
}