90分求助,TLE#2

P1434 [SHOI2002] 滑雪

CHGM @ 2024-07-16 15:35:37

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[105][105],dp[105][105],d;
struct node{
    int x,y,z;
};
struct cmp{
    bool operator()(node a,node b){
        return a.z>b.z;
    }
};
priority_queue<node,vector<node>,cmp > q;
bool in(int x, int y) {
    return 1<=x&&x<=n&&1<=y&&y<=m;
}
void dfs(int x,int y,long long z){
    if(in(x,y)==0||z<dp[x][y])return;
    dp[x][y]=z;
    d=max(d,z);
    if(a[x][y]<a[x+1][y])dfs(x+1,y,z+1);
    if(a[x][y]<a[x][y+1])dfs(x,y+1,z+1);
    if(a[x][y]<a[x-1][y])dfs(x-1,y,z+1);
    if(a[x][y]<a[x][y-1])dfs(x,y-1,z+1);
    return;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>a[i][j];q.push(node{i,j,a[i][j]});}
    while(q.size()){
        if(dp[q.top().x][q.top().y]==0)dfs(q.top().x,q.top().y,1);
        q.pop();
    }
    cout<<d;
    return 0;
}

|