样例没过玄关求条

Cute_Furina @ 2024-09-17 22:16:57

#include<bits/stdc++.h>
using namespace std;
struct node {
    int x, y, t;
}a[500005];
int f[410][410], m, ans, b[410][410];
int dx[5] = {0, 1, -1, 0, 0};
int dy[5] = {0, 0, 0, 1, -1};
bool cmp(node a, node b) {
    return a.t < b.t;
}
void dfs(int x, int y, int cnt) {
    //cout << x << " " << y <<" " << cnt << " " << f[x][y]<< endl;
    if(f[x][y] == 1e9) {
        cout << cnt << endl;
        exit(0);
    }
    for(int i = 1;i <= 4;i ++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(f[xx][yy] > cnt + 1 && xx < 400 && yy < 400 && xx >= 0 && yy >= 0 && b[xx][yy] == 0) {
            b[xx][yy] = 1;
            dfs(xx, yy, cnt + 1);
        }
    }
    cout << -1 << endl;
    exit(0);
}
signed main() {
    for(int i = 0;i < 400;i ++) {
        for(int j = 0;j < 400;j ++) {
            f[i][j] = 1e9;
        }
    }
    cin >> m;
    for(int i = 1;i <= m;i ++) {
        cin >> a[i].x >> a[i].y >> a[i].t;
    }
    sort(a + 1, a + m + 1, cmp);
    for(int i = 1;i <= m;i ++) {
        int x = a[i].x, y = a[i].y, t = a[i].t;
        f[x][y] = t;
        f[x - 1][y] = t;
        f[x + 1][y] = t;
        f[x][y - 1] = t;
        f[x][y + 1] = t;
    }
    dfs(0, 0, 0);
}

by Cute_Furina @ 2024-09-17 22:18:18

为什么他只会往下走

by 枫原万叶 @ 2024-09-17 22:29:44

@Luowj 用BFS好一点吧

by Cute_Furina @ 2024-09-17 22:31:24

@luogu_cyx dfs第一轮只往下走是怎么回事？

by 枫原万叶 @ 2024-09-17 22:35:41

@Luowj 你这个的dx和dy数组定义了移动的方向，分别是四个方向嘛。在dfs函数的循环中，遍历方向的顺序是固定的，可能导致在第一轮搜索时优先选择了向下的方向。

by Loyal_Soldier @ 2024-09-18 19:40:35

@Luowj

#include<bits/stdc++.h>
using namespace std;
int n,ans=INT_MAX;
int flag[1000][1000];
int tim[1000][1000];
int f[1000][1000];
int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1};
void dfs(int x,int y,int s){
    if(x<0||y<0||(flag[x][y]==1&&s>=tim[x][y])||s>=ans||s>=f[x][y])
        return;
    f[x][y]=s;
    if(flag[x][y]==0){
        ans=min(ans,s);
        return;
    }
    for(int i=1;i<=4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        dfs(nx,ny,s+1);
    }
}
int main(){
    memset(tim,0xa7f,sizeof(tim));
    memset(f,0xa7f,sizeof(f));
    cin>>n;
    for(int i=1;i<=n;i++){
        int t,x,y;
        cin>>x>>y>>t;
        flag[x][y]=1;
        tim[x][y]=min(tim[x][y],t);
        for(int j=1;j<=4;j++){
            int nx=x+dx[j],ny=y+dy[j];
            if(nx>=0&&ny>=0){
                flag[nx][ny]=1;
                if(t<tim[nx][ny])
                    tim[nx][ny]=t;
            }
        }
    }
    dfs(0,0,0);
    if(ans==INT_MAX){
        cout<<-1;
        return 0;
    }
    cout<<ans;
    return 0;
}

by Cute_Furina @ 2024-09-18 20:01:58

@luogu_cyx 但他没有搜向右的