BFS30pts超时
查看原帖
BFS30pts超时
615931
Qianmo_su楼主2023/3/31 20:02

超了很多

#include <iostream>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
#define int long long
const int N = 500;
int g[N][N],n,m,x,y;
bool vis[N][N];
int tx[] = {-1,-2,-2,-1,1,2,2,1},ty[] = {2,1,-1,-2,2,1,-1,-2};

inline void bfs()
{
    queue<PII> q;
    q.push({x,y});
    g[x][y] = 0;
    vis[x][y] = true;
    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        int xx = t.first,yy = t.second;
        for(int i=0;i<=7;i++)
        {
            int rx = xx+tx[i],ry = yy+ty[i];
            if(rx>=1 && rx<=n && ry>=1 && ry<=m && !vis[rx][ry])
            {
                q.push({rx,ry});
                g[rx][ry] = g[xx][yy]+1;
                vis[xx][yy] = true;
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> x >> y;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            g[i][j] = -1;
    bfs();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) printf("%-5d",g[i][j]);
        cout << endl;
    }
    return 0;
}
2023/3/31 20:02
加载中...