为啥用深搜能得90分?(虽然DP已经AC了)(困惑)
查看原帖
为啥用深搜能得90分?(虽然DP已经AC了)(困惑)
493738
hsx_std楼主2021/5/5 21:10
#include<bits/stdc++.h>
using namespace std;
int ans=1;
int r,c;
int a[105][105];
void dfs(int pos1,int pos2,int xzs)
{
	if(a[pos1][pos2]<a[pos1-1][pos2] && a[pos1][pos2]<a[pos1+1][pos2] && a[pos1][pos2]<a[pos1][pos2-1] && a[pos1][pos2]<a[pos1][pos2+1])
	{
		if(xzs+1>ans)	ans=xzs+1;
		return;
	}
	if(a[pos1][pos2]>a[pos1-1][pos2])	dfs(pos1-1,pos2,xzs+1);
	if(a[pos1][pos2]>a[pos1+1][pos2])	dfs(pos1+1,pos2,xzs+1);
	if(a[pos1][pos2]>a[pos1][pos2-1])	dfs(pos1,pos2-1,xzs+1);
	if(a[pos1][pos2]>a[pos1][pos2+1])	dfs(pos1,pos2+1,xzs+1);
}
int main()
{
	cin>>r>>c;
	for(int i=0;i<=r+1;i++)
	{
		a[i][0]=10000000;
		a[i][c+1]=10000000;
	}
	for(int i=0;i<=c+1;i++)
	{
		a[0][i]=10000000;
		a[r+1][i]=10000000;
	}
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=c;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=c;j++)
		{
			dfs(i,j,0);
		}
	}
	cout<<ans<<endl;
	return 0;
}
2021/5/5 21:10
加载中...