算法提高课汇总

算法思路

• 每次步数权值为1, 每步移动方式扩展为走日.

代码实现

#include <iostream>

#define x first
#define y second

using namespace std;

typedef pair<int, int> pii;

const int N = 155;

int n, m;
char g[N][N];
int dist[N][N];
pii q[N * N];

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

    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;

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

    while( hh < tt )
    {
        pii cur = q[hh ++];
        int x = cur.x, y = cur.y;
        for( int i = 0; i < 8; i ++ )
        {
            int nx = x + dx[i], ny = y + dy[i];
            if( nx < 0 || nx >= n || ny < 0 || ny >= m )    continue;
            if( g[nx][ny] == '*' )  continue;
            if( dist[nx][ny] )  continue;

            if( g[nx][ny] == 'H' )  return dist[x][y];

            dist[nx][ny] = dist[x][y] + 1;
            q[tt ++] = {nx, ny};
        }
    }
    return -1;
}

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

    cout << bfs() << endl;

    return 0;
}