看看我还有救吗
  • 板块灌水区
  • 楼主_wangleting123_
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/12/25 19:19
  • 上次更新2023/12/25 21:57:40
查看原帖
看看我还有救吗
1040559
_wangleting123_楼主2023/12/25 19:19
滑雪是一项非常刺激的运动,为了获得速度,滑雪的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。

给出一个由二维数组表示的滑雪区域,数组的数字代表各点的高度。请你找出这个区域中最长的滑坡。

下面是一个例子:

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。

在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然,25-24-23-...-3-2-1更长。事实上,这是最长的一条滑坡。
输入描述:

输入第一行为两个数R, C,表示滑雪区域的行数和列数(1≤R,C≤100)

下面是R行,每行有C个整数,表示高度H(0≤H≤10000)。
输出描述:

输出一行,只包含一个整数,表示滑雪区域中最长滑坡的长度。
#include <bits/stdc++.h>
using namespace std;
int a[10001][10001],x[10001],y[10001],a2[10001];
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int r,c,ma,s;
int ans=0;
void dfs(int x,int y)
{
	int tx,ty;
	ma=max(ma,s);
	for(int i=0;i<=3;i++)
	{
		tx=x+dx[i];
		ty=y+dy[i];
		if(ty>c||tx>r||tx<1||ty<1) continue;
		if(a[tx][ty]<a[x][y]){
		s+=1;
		dfs(tx,ty);
		s-=1;
		} 
	}
}

int main()
{
	cin>>r>>c;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=c;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=r*c;i++)
	{
		x[i]=floor(i/r)+1;
		y[i]=i%c;
		int x2=x[i];
		int y2=y[i];
		a2[i]=a[x2][y2];
	}
	for(int i=1;i<=r*c-1;i++)
	{
		for(int j=i+1;j<=r*c;j++)
		{
			if(a2[i]<a2[j])
			{
				swap(a2[i],a2[j]);
				swap(x[i],x[j]);
				swap(y[i],y[j]);
			}
		}
	}
	dfs(x[1],y[1]);
	dfs(x[2],y[2]);
	dfs(x[3],y[3]);
	dfs(x[4],y[4]);
	dfs(x[5],y[5]);
	dfs(x[6],y[6]);
	dfs(x[7],y[7]);
	dfs(x[8],y[8]);
	dfs(x[9],y[9]);
	dfs(x[10],y[10]);
	dfs(x[11],y[11]);
	dfs(x[12],y[12]);
	dfs(x[13],y[13]);
	dfs(x[14],y[14]);
	dfs(x[15],y[15]);
	dfs(x[16],y[16]);
	dfs(x[17],y[17]);
	dfs(x[18],y[18]);
	dfs(x[19],y[19]);
	dfs(x[20],y[10]);
	dfs(x[21],y[21]);
	dfs(x[22],y[22]);
	dfs(x[23],y[23]);
	dfs(x[24],y[24]);
	dfs(x[25],y[25]);
	dfs(x[26],y[26]);
	dfs(x[27],y[27]);
	dfs(x[28],y[28]);
	dfs(x[29],y[29]);
	dfs(x[30],y[30]);
	dfs(x[31],y[31]);
	dfs(x[32],y[32]);
	dfs(x[33],y[33]);
	dfs(x[34],y[34]);
	dfs(x[35],y[35]);
	dfs(x[35],y[35]);
	cout<<ma+1<<endl;
	return 0;
}

2023/12/25 19:19
加载中...