算法提高课汇总

算法思路

• $BFS$求最短路.

• 记录方案: 记忆数组, 记录当前位置的上一步.

具体代码

#include <cstring>
#include <iostream>

#define x first
#define y second

using namespace std;

typedef pair<int, int> pii;

const int N = 1010;

int n;
int g[N][N];
pii pre[N][N], q[N * N];

void bfs(int sx, int sy)
{
    const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

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

    while( hh < tt )
    {
        pii cur = q[hh ++];
        int x = cur.x, y = cur.y;
        for( int i = 0; i < 4; i ++ )
        {
            int nx = x + dx[i], ny = y + dy[i];
            if( nx < 0 || nx >= n || ny < 0 || ny >= n )    continue;
            if( g[nx][ny] || pre[nx][ny].x != -1 )    continue;

            pre[nx][ny] = {x, y};
            q[tt ++] = {nx, ny};
        }
    }
}

void print(int x, int y)
{
    if( x || y ) //x == 0 && y ==0 作为出口
        print(pre[x][y].x, pre[x][y].y);

    cout << x << ' ' << y << endl;
}

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

    bfs(0, 0);
    print(n - 1, n - 1);

    return 0;
}