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