DFS

AcWing 842. 排列数字

#include <iostream>

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++) cout << path[i] << ' ';
        puts("");
        return;
    }

    for (int i = 1; i <= n; i++)
    {
        if (!st[i])
        {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            //恢复现场
            //path[u] = 0;
            st[i] = false;
        }
    }
}

int main()
{
    cin >> n;

    dfs(0);

    return 0;
}

AcWing 843. n-皇后问题

第一种搜索顺序

#include <iostream>

using namespace std;

const int N = 20;

int n;
char map[N][N];
bool col[N], dg[N * 2], udg[N * 2];

void dfs(int u)
{
    if (u == n)   //搜索到n个皇后
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++) cout << map[i][j];
            puts("");
        }
        puts("");
        return;
    }

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

int main()
{
    cin >> n;

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

    dfs(0);

    return 0;
}

第二种搜索顺序

#include <iostream>

using namespace std;

const int N = 20;

int n;
char map[N][N];
bool row[N], col[N], dg[N * 2], udg[N * 2];

void dfs(int x, int y, int s)
{
      //扫描完一行，n-1是一列的最后一个位置，y到达n，就代表一行结束
      if (y == n) y = 0, x++;

      //0 ... n-1 行，当x = n，就代表n行都扫描完了
      if (x == n)
      {
          if (s == n)
          {
              for (int i = 0; i < n; i++) puts(map[i]);
              puts("");
          }
          return;
      }

      //不放
      dfs(x, y + 1, s);

      //放
      if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
      {
          map[x][y] = 'Q';
          row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
          dfs(x, y + 1, s + 1);
          row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
          map[x][y] = '.';
      }
}

int main()
{
    cin >> n;

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

    dfs(0, 0, 0);

    return 0;
}

AcWing 1112. 迷宫

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

char g[N][N];
bool st[N][N];

int xa, ya, xb, yb;
int n;

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

bool dfs(int x, int y)
{   
    if (g[x][y] == '#') return false;   //先要判断这个点是不是"#"
    if (x == ya && y == yb) return true;

    st[x][y] = true;
    for (int i = 0; i < 4; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= n) continue;
        if (st[a][b]) continue;

        st[a][b] = true;
        if (dfs(a, b)) return true;
    }

    return false;
}

int main()
{
    int M;
    cin >> M;

    while (M--)
    {
        cin >> n;

        for (int i = 0; i < n; i++) cin >> g[i];
        memset(st, false, sizeof st);

        cin  >> xa >> xb >> ya >> yb;

        if (dfs(xa, xb)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

AcWing 1113. 红与黑

#include <iostream>
#include <cstring>

using namespace std;

const int N = 25;

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

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

int dfs(int x, int y)
{
    int cnt = 1;

    st[x][y] = true;
    for (int i = 0; i < 4; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (g[a][b] != '.') continue;
        if (st[a][b]) continue;

        cnt += dfs(a, b);
    }

    return cnt;
}

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

        memset(st, 0, sizeof st);

        int x, y;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] == '@')
                    x = i, y = j;

        cout << dfs(x, y) << endl;
    }

    return 0;
}

AcWing 1116. 马走日

#include <iostream>
#include <cstring>

using namespace std;

const int N = 15;

int g[N][N];
bool st[N][N];
int ans;
int n, m, x, y;

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

void dfs(int x, int y, int cnt)
{
    if (cnt == n * m)
    {
        ans++;
        return ;
    }

    st[x][y] = 1;
    for (int i = 0; i < 8; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (st[a][b]) continue;

        st[a][b] = 1;
        dfs(a, b, cnt + 1);
        st[a][b] = 0;
    }
}

int main()
{
    int M;
    cin >> M;

    while (M--)
    {
        memset(st, 0, sizeof st);
        cin >> n >> m >> x >> y;
        ans = 0;

        dfs(x, y, 1);
        cout << ans << endl;
    }

    return 0;
}

AcWing 1117. 单词接龙

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 21;

string word[N];
int g[N][N];
int used[N];
int n;
int ans;

void dfs(string dragon, int last)
{
    ans = max((int)dragon.size(), ans);

    used[last]++;

    for (int i = 0; i < n; i++)
        if (g[last][i] && used[i] < 2)
            dfs(dragon + word[i].substr(g[last][i]), i);

    used[last]--;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> word[i];
    char start;
    cin >> start;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            string a = word[i], b = word[j];
            for (int k = 1; k < min(a.size(), b.size()); k++)
                if (a.substr(a.size()-k, k) == b.substr(0, k))
                {
                    g[i][j] = k;
                    break;            //两个单词接起来的字符串越短越好
                }
        }

    for (int i = 0; i < n; i++)
        if (word[i][0] == start)
            dfs(word[i], i);  //从word[i]开始搜，当前最后一个单词是i。记一下当前单词是i，判断下一个单词是不是能接

    cout << ans << endl;

    return 0;
}

AcWing 1118. 分成互质组

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 15;

int n;
int p[N];
int group[N][N];
bool st[N];
int ans = N;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

bool check(int group[], int gc, int i)
{
    for (int j = 0; j < gc; j++)
        if (gcd(p[group[j]], p[i]) > 1)
            return false;

    return true;
}

//搜第g组，当前组里有gc个元素，当前一共搜了tc个元素，这组从start号下标开始搜
void dfs(int g, int gc, int tc, int start)
{
    if (g >= ans) return ;
    if (tc == n) ans = g;

    bool flag = true;
    for (int i = start; i < n; i++)
        if (!st[i] && check(group[g], gc, i))
        {
            st[i] = true;
            group[g][gc] = i;
            dfs(g, gc + 1, tc + 1, i + 1);
            st[i] = false;

            flag = false;
        }

    //新开组    
    if (flag) dfs(g + 1, 0, tc, 0);
}

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

    dfs(1, 0, 0, 0); //搜第1组，当前组里有0个元素，当前一共搜了0个元素，这组从0号下标开始搜

    cout << ans << endl;

    return 0;
}

165. 小猫爬山

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;

int n, m;
int w[N];
int sum[N];
int ans = N;

void dfs(int u, int k) //搜索第u个小猫，开了k个车
{
    if (k >= ans) return ;//最优性剪枝
    if (k < ans && u == n)
    {
        ans = k;
        return ;
    }

    //可行性剪枝
    for (int i = 0; i < k; i++)
        if (sum[i] + w[u] <= m)
        {
            sum[i] += w[u];
            dfs(u + 1, k);  //搜索下一个，k个车不变
            sum[i] -= w[u];
        }

    //新开一辆车
    sum[k] = w[u];    //sum[k] 指第k+1个车
    dfs(u + 1, k + 1);
    sum[k] = 0;
}

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

    sort(w, w + n);
    reverse(w, w + n);

    dfs(0, 0);  //从第0号开始搜，已经搜了0个

    cout << ans << endl;

    return 0;
}

AcWing 166. 数独

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 9, M = 1 << N;

//打表
//ones[M]快速的求出来状态里有多少个1,map[]log2k
int ones[M], map[M];
int row[N], col[N], cell[3][3];
char str[100];

void init()
{
    //初始化每一位都是1，1代表可以用，1-9都可以用
    for (int i = 0; i < N; i++)
        row[i] = col[i] = (1 << N) - 1;

    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            cell[i][j] = (1 << N) - 1;
}

//辅助函数
//当前在x,y是把t填上，还是删掉（填就是dfs，删掉就是恢复现场的过程）
//1表示能用，0表示不能用
void draw(int x, int y, int t, bool is_set)
{
    if (is_set) str[x * N + y] = '1' + t; //t是0-8
    else str[x * N + y] = '.';

    int v = 1 << t;
    if (!is_set) v = -v;   //如果是清空操作，取反

    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v; 
}

int lowbit(int x)
{
    return x & -x;
}

int get(int x, int y)
{
    //哪一个数可以用
    return row[x] & col[y] & cell[x / 3][y / 3]; 
}

bool dfs(int cnt)
{
    if (!cnt) return true;   //当前没有宫格了，就找到合法方案

    int minv = 10;
    int x, y;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (str[i * N + j] == '.')
            {
                int state = get(i, j);
                if (ones[state] < minv)    //每个二进制数里1的个数
                {
                    minv = ones[state];
                    x = i, y = j;
                }
            }

    //循环完，xy存的是分支数量最少的格子
    //先看下这个格子能枚举哪个数
    int state = get(x, y);
    for (int i = state; i; i -= lowbit(i))
    {
        int t = map[lowbit(i)];  //lowbit(i)返回2的k次方，map一下，把2的k次方映射成k(1代表这个数可以填，map映射给t)
        draw(x, y, t, true);
        if (dfs(cnt - 1)) return true; //dfs下一层
        draw(x, y, t, false);
    }

    return false;
}

int main()
{
    for (int i = 0; i < N; i++) map[1 << i] = i;//2的i次幂作为下标，存的值为i
    for (int i = 0; i < 1 << N; i++)
        for (int j = 0; j < N; j++)
            ones[i] += i >> j & 1;   //每个数二进制表示有多少个1

    while (cin >> str, str[0] != 'e')
    {
        init();

        int cnt = 0;
        for (int i = 0, k = 0; i < N; i++)
            for (int j = 0; j < N; j++, k++)
                if (str[k] != '.')
                {
                    int t = str[k] - '1';  //先看下数字是多少
                    draw(i, j, t, true);   //在这个点填上t
                }
                else cnt++;                //否则就是空格

        dfs(cnt);

        puts(str);
    }

    return 0;
}

AcWing 167. 木棒

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 70;

int n;
int w[N], sum, length;
bool st[N];

bool dfs(int u, int s, int start)
{
    if (u * length == sum) return true;
    if (s == length) return dfs(u + 1, 0, 0);

    //i从start开始枚举
    for (int i = start; i < n; i++)
    {
        if (st[i]) continue;
        if (s + w[i] > length) continue;

        st[i] = true;
        if (dfs(u, s + w[i], i + 1)) return true;
        st[i] = false;

        //如果当前大棍的第一个小棍就失败的话，就return
        if (!s) return false;

        //如果当前大棍的最后一个小棍失败的话，就return
        if (s + w[i] == length) return false;

        //当前长度的失败了，等长的都不要试了
        int j = i;
        while (j < n && w[j] == w[i]) j++;
        i = j - 1;
    }

    return false;
}

int main()
{
    while (cin >> n, n)
    {
        memset(st, 0, sizeof st);
        sum = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> w[i];
            sum += w[i];
        }

        //优化搜索顺序
        sort(w, w + n);
        reverse(w, w + n);

        length = 1;
        while (true)
        {
            if (sum % length == 0 && dfs(0, 0, 0)) //枚举每一根大棍，每根长度为0，从0开始枚举
            {
                cout << length << endl;
                break;
            }
            length++;
        }
    }

    return 0;
}#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 70;

int n;
int w[N], sum, length;
bool st[N];

bool dfs(int u, int s, int start)
{
    if (u * length == sum) return true;
    if (s == length) return dfs(u + 1, 0, 0);

    //i从start开始枚举
    for (int i = start; i < n; i++)
    {
        if (st[i]) continue;
        if (s + w[i] > length) continue;

        st[i] = true;
        if (dfs(u, s + w[i], i + 1)) return true;
        st[i] = false;

        //如果当前大棍的第一个小棍就失败的话，就return
        if (!s) return false;

        //如果当前大棍的最后一个小棍失败的话，就return
        if (s + w[i] == length) return false;

        //当前长度的失败了，等长的都不要试了
        int j = i;
        while (j < n && w[j] == w[i]) j++;
        i = j - 1;
    }

    return false;
}

int main()
{
    while (cin >> n, n)
    {
        memset(st, 0, sizeof st);
        sum = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> w[i];
            sum += w[i];
        }

        //优化搜索顺序
        sort(w, w + n);
        reverse(w, w + n);

        length = 1;
        while (true)
        {
            if (sum % length == 0 && dfs(0, 0, 0)) //枚举每一根大棍，每根长度为0，从0开始枚举
            {
                cout << length << endl;
                break;
            }
            length++;
        }
    }

    return 0;
}

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;
}

AcWing 1098. 城堡问题

#include <iostream>
#include <algorithm>
#include <fstream>

#define x first
#define y second

using namespace std;

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

typedef pair<int, int> PII;

int g[N][N];
bool st[N][N];
PII q[M];

int n, m;

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

int idx, f[M];  //连通块编号，连通块的面积
int g_of_idx[N][N]; //记录每个方格属于哪个连通块
int max_area; //记录最大面积
int max_i = -1, max_j = -1;
char max_dir;
string dir = "WNES";

int bfs(int sx, int sy)
{   
    int area = 0;
    int hh = 0, tt = 0;   //模板hh = 0, tt = -1; 此处默认有一个start结点，tt = 0
    q[0].x = sx, q[0].y = sy;
    st[sx][sy] = true;

    idx++;       //每一个新队列，产生一个新的连通块

    while (hh <= tt)
    {
        area++;
        PII t = q[hh++];

        g_of_idx[t.x][t.y] = idx;   //标记这个方块属于哪个房间

        for (int i = 0; i < 4; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];

            //越界，被遍历过，continue
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (st[a][b]) continue;

            //这个方格是墙，就continue
            if (g[t.x][t.y] >> i & 1) continue;

            //入队
            ++tt;
            q[tt].x = a, q[tt].y = b;
            st[a][b] = true;
        }
    }

    f[idx] = area; //记录这个编号连通块的面积，记录在f[]里面

    return  area;
}   

int main()
{
    //freopen("P1457_4.in", "r", stdin);

    scanf("%d%d", &m, &n);

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

    int area = 0, cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            if (!st[i][j])
            {
                area = max(area, bfs(i, j));
                cnt++;
            }
        }

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

    for (int i = 0; i < n; i++)
        for (int j = m - 1; j >= 0; j--)
            for (int k = 1; k <= 2; k++)  //遍历每个方格的北面和东面，是否是墙，可以推倒
            {
                if ((g[i][j] >> k & 1) != 1) continue; //当前的方格不是墙，就要continue

                int tx = i + dx[k], ty = j + dy[k];
                if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue;

                if (g_of_idx[i][j] == g_of_idx[tx][ty]) continue;

                int sum_area = f[g_of_idx[i][j]] + f[g_of_idx[tx][ty]];
                if (sum_area > max_area)
                {
                    max_area = sum_area;
                    max_i = i;
                    max_j = j;
                    max_dir = dir[k];
                }
                else if (sum_area == max_area)
                {
                    //有多解时选最靠西的，仍然有多解时选最靠南的。同一格子北边的墙比东边的墙更优先。
                    if ((j == max_j && i > max_i) || (i == max_i && j < max_j))
                    {
                        max_area = sum_area;
                        max_i = i;
                        max_j = j;
                        max_dir = dir[k];
                    }

                }
            }

    printf("%d\n", max_area);
    printf("%d %d %c\n", max_i+1, max_j+1, max_dir);  //下标起始问题

    return 0;
}

AcWing 1106. 山峰和山谷

#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

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

int h[N][N];
bool st[N][N];
PII q[M];
int n;

void bfs(int sx, int sy, bool &have_higher, bool &have_lower)
{
    int hh = 0, tt = 0;
    q[tt] = {sx, sy};
    st[sx][sy] = true;

    while (hh <= tt)
    {
        PII t = q[hh++];

        for (int i = t.x - 1; i <= t.x + 1; i++)
            for (int j = t.y - 1; j <= t.y + 1; j++)
            {
                if (i == t.x && j == t.y) continue;

                if (i < 0 || i >= n || j < 0 || j >= n) continue;
                if (h[i][j] != h[t.x][t.y])
                {
                    if (h[i][j] > h[t.x][t.y]) have_higher = true;
                    else have_lower = true;
                }
                else
                {
                    if (st[i][j]) continue;

                    q[++tt] = {i, j};
                    st[i][j] = true;
                }
            }
    }
}

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

    int peek = 0, valley = 0;        
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (!st[i][j])       
            {
                bool have_higher = false, have_lower = false;
                bfs(i, j, have_higher, have_lower);

                if (!have_higher) peek++;   //用!have_higher的写法，省去了分支判断
                if (!have_lower) valley++;
            }

    cout << peek << ' ' << valley << endl;

    return 0;
}

AcWing 1076. 迷宫问题

#include <iostream>
#include <algorithm>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

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

int n;
int g[N][N];
PII q[M];
PII pre[N][N];

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

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

    memset(pre, -1, sizeof pre);
    pre[sx][sy] = {0, 0};
    while (hh <= tt)
    {
        PII t = q[hh++];

        for (int i = 0; i < 4; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0|| a >= n || b < 0 || b >= n) continue;

            if (g[a][b]) continue;
            if (pre[a][b].x != -1) continue;

            q[++tt] = {a, b};
            pre[a][b] = t;
        }
    }

}


int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &g[i][j]);

    bfs(n - 1, n - 1);

    PII end = {0, 0};
    while (true)
    {
        printf("%d %d\n", end.x, end.y);
        if (end.x == n - 1 && end.y == n - 1) break;
        end = pre[end.x][end.y];
    }

    return 0;
}

AcWing 188. 武士风度的牛

#include <iostream>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 160, M = N * N;
char g[N][N];
int dis[N][N];
PII q[M];
int n, m;

int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
//也可以这样写
//int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
//int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

int bfs()
{
    int sx, sy;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == 'K') sx = i, sy = j;

    int hh = 0, tt = 0;
    q[tt] = {sx, sy};

    memset(dis, -1, sizeof dis);
    dis[sx][sy] = 0;

    while (hh <= tt)
    {
        PII t = q[hh++];

        for (int i = 0; i < 8; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (dis[a][b] != -1) continue;

            if (g[a][b] == 'H') return dis[t.x][t.y] + 1;

            //入队操作
            q[++tt] = {a, b};
            dis[a][b] = dis[t.x][t.y] + 1;
        }
    }

    return -1;
}

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

    cout << bfs() << endl;

    return 0;
}

AcWing 1100. 抓住那头牛

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

int n, k;
int dist[N];
int q[N];

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

    memset(dist, -1, sizeof dist);
    dist[n] = 0;

    while (hh <= tt)
    {   
        int t = q[hh++];

        if (t == k) return dist[t];

        if (t + 1 <= N && dist[t + 1] == -1) 
        {   
            dist[t+1] = dist[t] + 1;
            q[++tt] = t + 1;
        }
        if (t - 1 >= 0 && dist[t - 1] == -1)
        {
            dist[t-1] = dist[t] + 1;
            q[++tt] = t - 1;
        }
        if (t * 2 <= N && dist[t * 2] == -1)
        {
            dist[t * 2] = dist[t] + 1;
            q[++tt] = t * 2;
        }
    }

    return -1;
}

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

    cout << bfs() << endl;

    return 0;
}