90分求助!

P1434 [SHOI2002] 滑雪

ZS_Lichi @ 2024-04-21 14:39:33

第二个点TLE

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int vis[N][N];
int mp[N][N];
int di[4] = {-1,1,0,0};
int dj[4] = {0,0,1,-1};
struct Node{
    int i,j,dis;
};
int n,m,maxn = 0, minn = 1000000,ans=0,si,sj,ei,ej;
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            cin >> mp[i][j];
        }
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            si = i;
            sj = j;
            memset(vis,0,sizeof(vis));
            queue <Node> q;
            vis[si][sj] = 1;
            q.push((Node){si,sj,1});
            while(!q.empty()){
                Node now = q.front();
                q.pop();
                ans = max(ans,now.dis);
                for(int k = 0;k < 4;k++){
                    int ni = now.i + di[k];
                    int nj = now.j + dj[k];
                    if(ni < 1 || nj < 1 || ni > n || nj > m || vis[ni][nj] >= now.dis+1 || mp[ni][nj] >= mp[now.i][now.j]) continue;
                    vis[ni][nj] = now.dis + 1;
                    q.push((Node){ni,nj,now.dis+1});
                }
            }
        }
    }

    cout << ans <<endl;
    return 0;
} 

by ayszYW @ 2024-05-25 12:38:03

加个记忆化就行了


|