题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<queue>

using namespace std;

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

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

int bfs(int x, int y, int c, int d)
{
    int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
    queue<PII> q;
    q.push({x, y});
    st[x][y] = true;

    int res = -1;
    while(q.size())
    {
        int size = q.size();
        res ++;
        while(size --)
        {
            auto t = q.front();
            q.pop();
            int x = t.first, y = t.second;
            if (x == c && y == d) return res;

            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 (str[a][b] == '*') continue;
                if (st[a][b]) continue;
                q.push({a, b});
                st[a][b] = true;
            }
        }
    }
    return -1;
}

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

    int a, b, c, d;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
        {
            if (str[i][j] == 'K') a = i, b = j;
            if (str[i][j] == 'H') c = i, d = j;
        }

    int res = bfs(a, b, c, d);

    cout << res;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla