92分代码,WA的最后一个点是50000个数据的输入,得到的是-1
  • 板块题目总版
  • 楼主dhm2048
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/9/24 09:45
  • 上次更新2024/9/24 16:30:47
查看原帖
92分代码,WA的最后一个点是50000个数据的输入,得到的是-1
1461605
dhm2048楼主2024/9/24 09:45

请教各位大佬看一下是哪个小细节没处理好

#include <bits/stdc++.h>
using namespace std;

int dx[5] = {0,0,1,-1};
int dy[5] = {1,-1,0,0};
constexpr int arr_size = 301,BIG = 99999999;
struct info
{
    int now_time,m_time;
    bool if_walk;
};
info Map_[arr_size][arr_size];

int main()
{
    int m;
    cin >> m;
    for (int i = 0; i < arr_size; i++)
    {
        for (int j = 0; j < arr_size; j++)
        {
            Map_[i][j].now_time = 0; // 记录走到这里花了多少时间
            Map_[i][j].if_walk = false;
            Map_[i][j].m_time = BIG;
        }
    }
    for (int i = 1; i <= m; i++)
    {
        int x,y,t;
        cin >> x >> y >> t;
        Map_[x][y].m_time = min(Map_[x][y].m_time,t);
        for (int j = 0; j < 4; j++)
        {
            if (x + dx[j] < 0 || x + dx[j] >=arr_size || y + dy[j] < 0 || y + dy[j] >= arr_size)
            {
                continue;
            }
            Map_[x + dx[j]][y + dy[j]].m_time = min( Map_[x + dx[j]][y + dy[j]].m_time, t );
        }
    }
    queue<pair<int,int>> Q;
    Q.push(make_pair(0,0));
    Map_[0][0].if_walk = true;
    while (Q.size() != 0)
    {
        pair<int,int> item = Q.front();
        Q.pop();
        info stand_node = Map_[item.first][item.second];
        if (stand_node.m_time == BIG)
        {
            cout << stand_node.now_time;
            return 0;
        }
        if (stand_node.m_time != BIG && stand_node.now_time >= stand_node.m_time)
        {
            continue;
        }
        for (int i = 0; i < 4; i++)
        {
            int ne_x = item.first + dx[i];
            int ne_y = item.second + dy[i];
            info& ne_node = Map_[ne_x][ne_y]; 
            if ((ne_x<0||ne_x>=arr_size||ne_y<0||ne_y>=arr_size)||Map_[ne_x][ne_y].if_walk)
                continue; // 检查越界和是否已经走过
            
            ne_node.if_walk = true;
            ne_node.now_time = stand_node.now_time + 1;

            Q.push(make_pair(ne_x,ne_y)); 
        }
    }
    cout << -1;
    return 0;
}
2024/9/24 09:45
加载中...