AcWing 168. 生日蛋糕
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 25, INF = 1e9;

int n, m;
int minv[N], mins[N];
int R[N], H[N];
int ans = INF;

void dfs(int u, int v, int s)//从第u层开始，当前体积v，当前面积s
{
    if (v + minv[u] > n) return ;  //体积大于n，剪枝
    if (s + mins[u] >= ans) return ; //面积比当前ans大，剪枝
    if (s + 2 * (n - v) / R[u + 1] >= ans) return ; //最优性剪枝 算法进阶指南P108

    if (!u)
    {
        if (v == n) ans = s;
        return ;
    }

    for (int r = min(R[u + 1] - 1, (int)sqrt(n - v)); r >= u; r--)
        for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; h--)
        {
            int t = 0;
            if (u == m) t = r * r; //最后一层，算一下封盖的面积

            R[u] = r, H[u] = h;
            dfs(u - 1, v + r * r * h, s + 2 * r * h + t);//从第u-1层开始，当前体积v+r*r*h，当前面积s+2*r*h+t
        }
}

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

    //打表处理每一行最小的体积和面积，自底向上，每一层严格小于上一层的半径和高度
    for (int i = 1; i <= m; i++)
    {
        minv[i] = minv[i - 1] + i * i * i;    //体积：i*i  *i
        mins[i] = mins[i - 1] + 2 * i * i;    //面积：2*i  *i
    }

    R[m + 1] = H[m + 1] = INF;

    dfs(m, 0, 0);//从第m层开始，当前体积和面积都是0

    cout << ans << endl;

    return 0;
}
BFS
AcWing 844. 走迷宫
用数组

#include <iostream>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 200;

int n, m;
int g[N][N];
int d[N][N];
PII q[N * N], Prev[N][N];

int bfs()
{
    int hh = 0, tt = 0;
    q[0] = {0, 0};

    memset(d, -1, sizeof(d));

    d[0][0] = 0;
    //四个方向的向量
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (hh <= tt)
    {
        PII t = q[hh++];
        for (int i = 0; i < 4; i++)
        {   int x = t.first + dx[i], y = t.second + dy[i];
            //if (x >= 0 && x < n && y >= 0 && y < n && g[x][y] == 0 && d[x][y] == -1)  打错字母了
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) 
            {
                d[x][y]= d[t.first][t.second] + 1;
                Prev[x][y] = t;
                q[++tt] = {x, y};
            }
        }
    }

/*    
    int x = n - 1, y = m - 1;
    while (x || y)
    {
        cout << x << ' ' << y << endl;
        PII t = Prev[x][y];
        x = t.first, y = t.second;
    }
*/  
    return d[n - 1][m - 1];
}

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

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

    cout << bfs() << endl;

    /*
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            printf("%3d", d[i][j]);
        cout << endl;
    }
    */

    return 0;
}
用queue写

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

using namespace std;

const int N = 110;

typedef pair<int, int> PII;

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

int bfs()
{
    queue< pair<int, int> > q;
    memset(d, -1, sizeof(d));
    d[0][0] = 0;
    q.push({0, 0});

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
    while (q.size())
    {
        PII 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 >= 0 && x < n && y >= 0 && 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 - 1][m -1];
}

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

    cout << bfs() << endl;

    return 0;
}
AcWing 845. 八数码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <bits/stdc++.h>

using namespace std;

int bfs(string start)
{
    string end = "12345678x";

    queue<string> q;
    unordered_map<string, int> d;
    q.push(start);    
    d[start] = 0;

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

    while (q.size())
    {
        string t = q.front();
        q.pop();
        int dis = d[t];

        if (t == end) return d[t];

        int k = t.find('x');
        int x = k / 3, y = k % 3;

        for (int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                swap(t[k], t[a * 3 + b]);

                if (!d.count(t))  //第一次出现
                {
                    q.push(t);
                    d[t] = dis + 1;   
                }

                swap(t[k], t[a * 3 + b]);  //一个方向尝试完，要复原一下，尝试下一个方向
            }
        }
    }

    return -1;
}

int main()
{
    string start, c;

    for (int i = 0; i < 9; i++)
    {
        cin >> c;
        start += c;
    }

    cout << bfs(start) << endl;

    return 0;
}
AcWing 1097. 池塘计数
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int > PII;

const int N = 1010, M = N * N;

PII q[M];
char g[N][N];
bool st[N][N];
int n, m;

void bfs(int xx, int yy)
{
    //队列初始化
    int hh = 0, tt = 0;
    q[0].first = xx, q[0].second = yy;
    st[xx][yy] = true;

    while (hh <= tt)
    {
        PII t = q[hh++];   //取队头，数组模拟队列   

        for (int i = t.first - 1; i <= t.first + 1; i++)
            for (int j = t.second - 1; j <= t.second + 1; j++)
            {
                if (i < 0 || i >= n || j < 0 || j >= m) continue;
                if (i == t.first && j == t.second) continue;   //中间那块挖掉
                if (g[i][j] == '.') continue;
                if (g[i][j] == 'W' && st[i][j]) continue;

                ++tt;
                q[tt].first = i, q[tt].second = j;
                st[i][j] = true;
            }
    }
}

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

    for (int i = 0; i < n; i++)
    {
        getchar();
        for (int j = 0; j < m; j++) scanf("%c", &g[i][j]);
    }

    int cnt = 0;    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            if (!st[i][j] && g[i][j] == 'W')  //是一个新的连通块，就BFS进去
            {
                cnt++;
                bfs(i, j);
            }
        }

    printf("%d\n", cnt);

    return 0;
}