两个队列来回倒,几乎和题解一样啊,为什么3~9会超时呢
  • 板块P1443 马的遍历
  • 楼主JK01WYX
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/13 20:43
  • 上次更新2023/11/13 21:31:48
查看原帖
两个队列来回倒,几乎和题解一样啊,为什么3~9会超时呢
798434
JK01WYX楼主2023/11/13 20:43

都弄成,bfs,-1就填depth

#define _CRT_SECURE_NO_WARNINGS 1
//#include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
using namespace std;
#include <unordered_map>
#include <vector>
#include <math.h> 
#include <list> 
#include <map> 
#include <stack>
#include <queue>
#include <set>
#include <unordered_set>
#include <string>
#include <algorithm>//sort
#include <stdlib.h>
#include <iomanip>
#include <cstring>//memset
#include <limits.h>

int fx[8] = {1,2,1,2,-1,-2,-1,-2};
int fy[8] = {2,1,-2,-1,2,1,-2,-1};
int arr[509][509] = { 0 };
int n, m, x, y;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> x >> y;
    memset(arr, -1, sizeof(arr));
    queue<pair<int, int>>q1;
    queue<pair<int, int>>q2;
    q1.push({ x,y });
    int depth = 0;
    while (1)
    {
        int bx = q1.front().first, by = q1.front().second;
        arr[bx][by] = depth;
        q1.pop();
        for (int i = 0; i < 8; i++)
        {
            int aimx = bx + fx[i], aimy = by + fy[i];
            if (aimx >= 1 && aimx <= n
                && aimy >= 1 && aimy <= m
                && arr[aimx][aimy] == -1)
            {
                q2.push({aimx,aimy});
            }
        }
        if (q1.empty())
        {
            if (q2.empty())break;
            depth++;
            swap(q1, q2);
            //q1 = q2;
            //q2 = queue<pair<int, int>>();
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            printf("%-5d", arr[i][j]);
        }
        cout << endl;
    }
    return 0;
}
2023/11/13 20:43
加载中...