记忆化搜索80分求助!
查看原帖
记忆化搜索80分求助!
539337
风起,即行楼主2021/7/24 14:41
#include <bits/stdc++.h>
using namespace std;
int r,c,m[105][105],ans[105][105],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int dfs(int x,int y)
{
	if(ans[x][y]!=0) return ans[x][y];
	if((m[x+1][y]<m[x][y])&&(m[x][y+1]<m[x][y])&&(m[x-1][y]<m[x][y])&&(m[x][y-1]<m[x][y]))//搜索时从低往高搜
	//利用初值为零数组可以不设边界 
	{
		return 1;
		//最高点初始长度为一 
	}
	int maxh=0;
	for(int i=0;i<4;i++)
	{
		int x1=x+dx[i],y1=y+dy[i];
		if((x1>0)&&(x1<=r)&&(y1>0)&&(y1<=c)&&(m[x1][y1]>m[x][y]))
		{
			maxh=max(dfs(x1,y1)+1,maxh);//搜索完某一点四个方向最值之后再确定该点的值 
		}
	}
	ans[x][y]=maxh;//把最值存入
	return maxh;
}
int main(){
	scanf("%d%d",&r,&c);
	int minh=99999999,p,q,maxh=1;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=c;j++)
		{
			scanf("%d",&m[i][j]);
		}
	}
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=c;j++)
		{
			dfs(i,j);
		}
	}
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=c;j++)
		{
			if(ans[i][j]>maxh)
			{
				maxh=ans[i][j];
			}
		}
	}
	printf("%d",maxh);
	return 0;
}
2021/7/24 14:41
加载中...