一种另类的思路
2025-10-05 16:25:04
发布于：广东
27阅读
0回复
0点赞
这题能用最短路做吗？
全部评论 3
我好像真把他缩短了
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=0x3f; ll xx[4]={0,-1,1,0},yy[4]={-1,0,0,1},n,m,ans,a[105][105],w[105][105]; ll f(ll x,ll y){if(w[x][y])return w[x][y];w[x][y]=1;for(int i=0;i<4;i++){ll dx=x+xx[i],dy=y+yy[i];if(dx<=n&&dx>=1&&dy>=1&&dy<=m&&a[x][y]>a[dx][dy])f(dx,dy),w[x][y]=max(w[x][y],w[dx][dy]+1);}return w[x][y];} int main(){cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ans=max(ans,f(i,j));cout<<ans;return 0;}3天前 来自 浙江
0最短路是这样吗
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=105; ll xx[]={0,-1,1,0},yy[]={-1,0,0,1}; ll n,m,a[N][N],d[N][N]; struct node{int x,y;ll w;}; bool operator<(node a,node b){return a.w>b.w;} int main(){ cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)cin>>a[i][j],d[i][j]=-1e18; priority_queue<node>q; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)q.push({i,j,1}),d[i][j]=1; ll ans=0; while(!q.empty()){ auto u=q.top();q.pop(); int x=u.x,y=u.y; if(u.w<d[x][y])continue; ans=max(ans,d[x][y]); for(int i=0;i<4;i++){ int dx=x+xx[i],dy=y+yy[i]; if(dx<1||dx>n||dy<1||dy>m)continue; if(a[x][y]>a[dx][dy]&&d[dx][dy]<d[x][y]+1){ d[dx][dy]=d[x][y]+1; q.push({dx,dy,d[dx][dy]}); } } } cout<<ans; }3天前 来自 浙江
0
有帮助，赞一个