A

#include <bits/stdc++.h>
using namespace std;

const int N = 200;
char G[N][N];
int n, m, sx, sy, ex, ey;
int dis[N][N];

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

void bfs() {
    queue<pair<int, int>> q;
    q.push({sx, sy});
    dis[sx][sy] = 0;
    G[sx][sy] = '*';

    while (q.size()) {
        auto t = q.front(); q.pop();
        int x = t.first, y = t.second;

        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (G[nx][ny] == '*') continue;

            q.push({nx, ny});
            dis[nx][ny] = dis[x][y] + 1;
            G[nx][ny] = '*';
        }
    }

    cout << dis[ex][ey] << endl;
}

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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (G[i][j] == 'K') {
                sx = i, sy = j;
            } else if (G[i][j] == 'H') {
                ex = i, ey = j;
            }
        }
    }

    bfs();
    
    return 0;
}

B

#include <bits/stdc++.h>
using namespace std;

const int N = 200;
int G[N][N];
int n, m, A, B, sx, sy, ex, ey;
int dis[N][N];

void bfs() {
    queue<pair<int, int>> q;
    q.push({sx, sy});

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


    int dx[8] = { A, A,-A,-A, B, B,-B,-B };
    int dy[8] = { B,-B, B,-B, A,-A, A,-A };

    while (q.size()) {
        auto t = q.front(); q.pop();
        int x = t.first, y = t.second;

        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (G[nx][ny] == 0 || G[nx][ny] == 2 || dis[nx][ny] != -1) continue;

            q.push({nx, ny});
            dis[nx][ny] = dis[x][y] + 1;
        }
    }

    cout << dis[ex][ey] << endl;
}

int main() {
    cin >> n >> m >> A >> B;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> G[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (G[i][j] == 3) {
                sx = i, sy = j;
            } else if (G[i][j] == 4) {
                ex = i, ey = j;
            }
        }
    }

    bfs();
    
    return 0;
}

C

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int x, y;
};
const int N = 105;
char g[N][N];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int d[N][N];
int n, sx, sy, ex, ey;

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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] == 'A') {
                sx = i;
                sy = j;
            }
            if (g[i][j] == 'B') {
                ex = i;
                ey = j;
            }
        }
    }

    memset(d, 0x3f, sizeof d);
    queue<Node> q;
    q.push({sx, sy});
    d[sx][sy] = 0;

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

        int x = t.x, y = t.y;
        if (x == ex && y == ey) break;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            while (nx >= 0 && nx < n && ny >= 0 && ny < n && g[nx][ny] != 'x') {
                if (d[nx][ny] > d[x][y] + 1) {
                    d[nx][ny] = d[x][y] + 1;
                    q.push({nx, ny});
                }
                nx += dx[i], ny += dy[i];
            }
        }
    }

    cout << (d[ex][ey] == 0x3f3f3f3f ? -1 : d[ex][ey] - 1) << endl;

    return 0;
}

D

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 1010;

char g[N][N];
PII pre[N][N];

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

void bfs() {
    memset(pre, -1, sizeof pre);

    queue<PII> q;
    q.push({n - 1, m - 1});

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

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

            if(a >= 0 && a < n && b >= 0 && b < m && g[a][b] == '.' && pre[a][b].first == -1) {
                q.push({a, b});
                pre[a][b] = t;
            }
        }
    }
}

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

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

    bfs();

    PII end(0, 0);

    while(true) {
        cout << end.first + 1 << " " << end.second + 1 << endl;
        if(end.first == n - 1 && end.second == m - 1) break;
        end = pre[end.first][end.second];
    }

    return 0;
}

E

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 1010;

struct Node {
    int h, x, y;
};

int G[N][N], vis[N][N];
int n, m;
int dx[] = {0, 0, 1, -1, -1, -1, 1, 1};
int dy[] = {1, -1, 0, 0, -1, 1, -1, 1};

bool cmp(const Node& a, const Node& b) {
    return a.h > b.h;
}

void bfs(int x, int y) {
    queue<PII> q;
    q.push({x, y});
    vis[x][y] = 0;

    while (!q.empty()) {
        PII t = q.front(); q.pop();
        int x = t.first, y = t.second;

        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];

            if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
            if (G[nx][ny] == 0) continue;
            if (vis[nx][ny]) continue;
            if (G[nx][ny] > G[x][y]) continue;

            q.push({nx, ny});
            vis[nx][ny] = 1;
        }
    }
}


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

    vector<Node> v;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> G[i][j];
            v.push_back({G[i][j], i, j});
        }
    }

    sort(v.begin(), v.end(), cmp);

    int ans = 0;
    for (int i = 0; i < v.size(); i++) {
        if (v[i].h == 0 || vis[v[i].x][v[i].y]) continue;
        ans++;
        bfs(v[i].x, v[i].y);
    }

    cout << ans << endl;

    return 0;
}