求助 前四个点能过

P2895 [USACO08FEB] Meteor Shower S

FL蛙AGS @ 2021-11-10 10:14:36

#include <bits/stdc++.h>
#include <utility>//pair的头文件
#include <queue>
using namespace std;
int fx[5] = { 0,1,-1,0,0 };
int fy[5] = { 0,0, 0,1,-1 };//方向数组
queue< pair<int, int> >q;
int a[350][350] = { 0 };//初始化为0 a用来模拟地图 
int ans[350][350] = { 0 }; //ans记录答案
int t[350][350];//记录陨石掉落的时间

int main()
{
    int num;
    cin >> num;
    memset(t, -1, sizeof(t));
    while (num--)
    {
        int x, y, ti;
        cin >> x >> y >> ti;
        if (ti < t[x][y] || t[x][y] == -1)
        {
            t[x][y] = ti;//记录最早掉落的陨石    
        }
        for (int i = 0; i < 5; i++)
        {
            if ((x + fx[i]) >= 0 && (y + fy[i]) >= 0 && (ti <= t[x][y] || t[x][y] == -1))
                t[x + fx[i]][y + fy[i]] = ti;
            //上下左右本身 都标记为ti  不能走
        }
    }//这个while 记录所有的陨石到达的时间 后面再进行判断能不能走

    //for (int i = 0; i < 10; i++)
    //{
    //  for (int j = 0; j < 10; j++)
    //      cout <<t[i][j];
    //  cout << endl;
    //}

    q.push(make_pair(0, 0));//让 0.0坐标形成pair并进入队列
    a[0][0] = 1;//记录为1  已经访问过  
    while (!q.empty())//队列不为空
    {
        //对队列内元素处理
        for (int i = 0; i < 5; i++)
        {
            int tx = q.front().first + fx[i];
            int ty = q.front().second + fy[i];
            //处理队列内第一个元素
            int now = ans[q.front().first][q.front().second] + 1; //现在的时间是当前点 +1 
            if (tx >= 0 && ty >= 0 && a[tx][ty] == 0 && (now < t[tx][ty] || t[tx][ty] == -1))
                //不越界 没被访问过 当前时间小于陨石落下的时间
            {
                a[tx][ty] = 1;//被走过
                ans[tx][ty] = now;// ans里面的点就是现在要记录的时间
                q.push(make_pair(tx, ty));

                if (t[tx][ty] == -1)
                {
                    cout << ans[tx][ty];
                    return 0;
                }
            }
        }
        q.pop();//退出
    }
    cout << -1;
    return 0;
}

by FL蛙AGS @ 2021-11-10 10:35:50

问题解决了 判断焦土的时候错了


|