Novicelpx @ 2021-11-11 15:06:18
第5个点和第7个点wa了
思路是从高度最小的点开始
每一个点的步数为它周围四格点的最大步数加一
不知道哪里有问题...恳请奆犇指点！
#include<bits/stdc++.h>
using namespace std;
struct T{
int high,step;
}mapp[1007][1007];
struct Y{
int x,y,highh;
}sor[1000007];
bool Cmp(Y a,Y b){
return a.highh<b.highh;
}
int find(int xx,int yy){
int ax[5],ay[5],hmy=0;
if(mapp[xx-1][yy].high<mapp[xx][yy].high&&mapp[xx-1][yy].high!=0){
hmy++;
ax[hmy]=xx-1;
ay[hmy]=yy;
}
if(mapp[xx+1][yy].high<mapp[xx][yy].high&&mapp[xx+1][yy].high!=0){
hmy++;
ax[hmy]=xx+1;
ay[hmy]=yy;
}
if(mapp[xx][yy+1].high<mapp[xx][yy].high&&mapp[xx][yy+1].high!=0){
hmy++;
ax[hmy]=xx;
ay[hmy]=yy+1;
}
if(mapp[xx][yy-1].high<mapp[xx][yy].high&&mapp[xx][yy-1].high!=0){
hmy++;
ax[hmy]=xx;
ay[hmy]=yy-1;
}
if(hmy==0)return mapp[xx][yy].step=1;
if(hmy==1)return mapp[xx][yy].step=mapp[ax[1]][ay[1]].step+1;
if(hmy==2)return mapp[xx][yy].step=max(mapp[ax[1]][ay[1]].step+1,mapp[ax[2]][ay[2]].step+1);
if(hmy==3)return mapp[xx][yy].step=max(mapp[ax[3]][ay[3]].step+1,max(mapp[ax[1]][ay[1]].step+1,mapp[ax[2]][ay[2]].step+1));
if(hmy==4)return mapp[xx][yy].step=max(mapp[ax[4]][ay[4]].step+1,max(mapp[ax[3]][ay[3]].step+1,max(mapp[ax[1]][ay[1]].step+1,mapp[ax[2]][ay[2]].step+1)));
}
int now,ans=0;
int main(){
int nx,ny;
cin>>nx>>ny;
for(int i=1;i<=nx;i++){
for(int j=1;j<=ny;j++){
scanf("%d",&mapp[i][j].high);
mapp[i][j].step=1;
sor[++now].x=i;
sor[now].y=j;
sor[now].highh=mapp[i][j].high;
}
}
sort(sor+1,sor+now+1,Cmp);
for(int i=1;i<=now;i++){
ans=max(ans,find(sor[i].x,sor[i].y));
}
cout<<ans;
return 0;
}by ningago @ 2021-11-11 15:30:51
@Novicelpx
把mapp.high初始化-1 高度可以为0
#include<bits/stdc++.h>
using namespace std;
struct T{
int high,step;
}mapp[1007][1007];
struct Y{
int x,y,highh;
}sor[1000007];
bool Cmp(Y a,Y b){
return a.highh<b.highh;
}
int find(int xx,int yy){
int ax[5],ay[5],hmy=0;
if(mapp[xx-1][yy].high<mapp[xx][yy].high&&mapp[xx-1][yy].high!=-1){
hmy++;
ax[hmy]=xx-1;
ay[hmy]=yy;
}
if(mapp[xx+1][yy].high<mapp[xx][yy].high&&mapp[xx+1][yy].high!=-1){
hmy++;
ax[hmy]=xx+1;
ay[hmy]=yy;
}
if(mapp[xx][yy+1].high<mapp[xx][yy].high&&mapp[xx][yy+1].high!=-1){
hmy++;
ax[hmy]=xx;
ay[hmy]=yy+1;
}
if(mapp[xx][yy-1].high<mapp[xx][yy].high&&mapp[xx][yy-1].high!=-1){
hmy++;
ax[hmy]=xx;
ay[hmy]=yy-1;
}
if(hmy==0)return mapp[xx][yy].step=1;
if(hmy==1)return mapp[xx][yy].step=mapp[ax[1]][ay[1]].step+1;
if(hmy==2)return mapp[xx][yy].step=max(mapp[ax[1]][ay[1]].step+1,mapp[ax[2]][ay[2]].step+1);
if(hmy==3)return mapp[xx][yy].step=max(mapp[ax[3]][ay[3]].step+1,max(mapp[ax[1]][ay[1]].step+1,mapp[ax[2]][ay[2]].step+1));
if(hmy==4)return mapp[xx][yy].step=max(mapp[ax[4]][ay[4]].step+1,max(mapp[ax[3]][ay[3]].step+1,max(mapp[ax[1]][ay[1]].step+1,mapp[ax[2]][ay[2]].step+1)));
}
int now,ans=0;
int main(){
int nx,ny;
cin>>nx>>ny;
for(int i = 0;i <= nx + 1;i++)
for(int j = 0;j <= ny + 1;j++)
mapp[i][j].high = -1;
for(int i=1;i<=nx;i++){
for(int j=1;j<=ny;j++){
scanf("%d",&mapp[i][j].high);
mapp[i][j].step=1;
sor[++now].x=i;
sor[now].y=j;
sor[now].highh=mapp[i][j].high;
}
}
sort(sor+1,sor+now+1,Cmp);
for(int i=1;i<=now;i++){
ans=max(ans,find(sor[i].x,sor[i].y));
}
cout<<ans;
return 0;
}ps.这题个人认为你的做法有点复杂，应该记忆化搜索。
by Novicelpx @ 2021-11-11 15:48:15
@ningago %%犇犇！十分感谢你，我会尝试记忆化的a.a