搜索复习

DFS

AcWing 842.排列数字

#include <iostream>
#include <cstdio>

using namespace std;
const int N = 10;

int n;
int path[N];
bool st[N];

void dfs(int u)
{
    if (u == n) 
    {
        for (int i = 0; i < n; i ++ ) printf("%d ", path[i]);
        puts("");
        return ;
    }


    for (int i = 1; i <= n; i ++ )
    {
        if (!st[i])
        {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
        }
    }
}

int main()
{
    cin >> n;

    dfs(0);

    return 0;
}

AcWing 843.n-皇后问题

#include <iostream>
#include <cstdio>

using namespace std;
const int N = 10;

char g[N][N];
int n;
bool col[N], dp[N], udp[N];

void dfs(int u)
{
    if (u == n)
    {
        for (int i = 0; i < n; i ++ ) puts(g[i]);
        puts("");
    }

    for (int i = 0; i < n; i ++ )
    {
        if (!col[i] && !dp[u + i] && !udp[n - i + u])
        {
            g[u][i] = 'Q';
            col[i] = dp[u + i] = udp[n - i + u] = true;
            dfs(u + 1);
            col[i] = dp[u + i] = udp[n - i + u] = false;
            g[u][i] = '.'; 
        }
    }
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';

    dfs(0);

    return 0;
}

BFS

AcWing 844.走迷宫

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;
typedef pair<int, int> PII;

const int N = 110;

int n, m;
int g[N][N];
int d[N][N];

queue <PII> q;

int bfs()
{
    memset(d, -1, sizeof d);

    int dx[5] = { 0, 1, 0, -1 }, dy[5] = { 1, 0, -1, 0 };

    d[1][1] = 0;

    q.push({1, 1});

    while (!q.empty())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }

    return d[n][m];
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];

    cout << bfs() << endl;

    return 0;
}