写的DFS、连样例都过不了。

P2895 [USACO08FEB] Meteor Shower S

小豆子范德萨 @ 2020-04-21 14:27:28

调了半天BUG了做不出来、帮下呀

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4+10;
int broke[310][310];        //broke[i][j] = i代表需要在i之前到达才可以(i都不行)
bool vis[310][310];
int ans = 1e9;
int dir[4][2] = {
    {-1,0},
    {1,0},
    {0,-1},
    {0,1}
};

bool inside(int x,int y) {
    if(x < 0 || y < 0) return false;
    return  true;
}

void dfs(int x,int y,int time) {
    if(time >= ans || broke[x][y] <= time) return;
    if(broke[x][y] == 1e9) {
        ans = min(ans,time);
        return;
    }

    vis[x][y] = true;       //防止重复访问,环的情况
    for(int k = 0;k < 4;k++) {
        int newx = x + dir[k][0];
        int newy = y + dir[k][1];
        if(inside(newx,newy) && !vis[newx][newy] && broke[newx][newy] > time) {
            dfs(newx,newy,time+1);
        }
    }
}

int main() {
    int n;cin>>n;
    int t,x,y;
    fill(broke[0],broke[0]+310*310,1e9);        //默认都可达
    broke[0][0] = 1;
    for(int i = 1;i <= n;i++) {
        cin>>t>>x>>y;
        broke[x][y] = min(broke[x][y],t);       //点燃中间(需要存储时间最小的)
        if(inside(x+1,y)) {     //点燃四周
            broke[x+1][y] = min(broke[x+1][y],t);
        }
        if(inside(x-1,y)) {
            broke[x-1][y] = min(broke[x-1][y],t);
        }
        if(inside(x,y-1)) {
            broke[x][y-1] = min(broke[x][y-1],t);
        }
        if(inside(x,y+1)) {
            broke[x][y+1] = min(broke[x][y+1],t);
        }
    }
    dfs(0,0,0);
    cout<<ans;
    return 0;
}

by metaphysis @ 2020-04-22 12:36:48

@小豆子范德萨

您能用您自己的话描述一下解题逻辑吗?这样做,既方便别人判断您的解题思路是否正确,也有利于您自己理清解题思路,以便于后续检查代码实现是否存在问题。


by 小豆子范德萨 @ 2020-04-22 13:34:42

就像我代码中写到的。 读入这块:

搜索这块: 从(0,0)开始dfs搜索、判断周围的 是否没有被烧焦(这里用时间来判断)


by metaphysis @ 2020-04-22 16:00:55

@小豆子范德萨

(1)题目翻译有问题,流星的数据格式是 X_i Y_i T_i

(2)您在初始化时将原点的撞击时间设置为1,不知为何原因?

您先处理上述两个问题,然后再看看。


by metaphysis @ 2020-04-22 16:06:39

输出时,当无解时,需要输出-1。


by 小豆子范德萨 @ 2020-04-22 20:57:03

@metaphysis 谢谢点播


|