记忆化搜索问题,怎么得了80分?
查看原帖
记忆化搜索问题,怎么得了80分?
463562
Dreamerlee✅楼主2021/4/6 17:26

求大佬帮忙,怎么不能ac?我写的记忆化搜索逻辑不太顺畅,往大佬指点

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int r, c, a[110][110], b[110][110], sum, tns = -0x7777777,ans=-0x7777777;
int dx[5] = { 0,1,-1,0,0 };
int dy[5] = { 0,0,0,-1,1 };
int dfs(int x, int y, int t)//t代表步数
{
	if (b[x][y])
		return t + b[x][y];//步数加上之前记忆的数组的值
	b[x][y] = 1;//既然这是一个从未走过的点那么现在来到该点至少都会使其步数为1 
	for (int i = 1; i <= 4; i++)
	{
		int px = x + dx[i];
		int py = y + dy[i];
		if (px >= 1 && px <= r && py >= 1 && py <= c)//不越界
		{
			if (a[px][py] < a[x][y])//滑雪只能滑向高度小的坐标
			{
				sum = max(ans,dfs(px, py, t + 1));//步数t每次加+1,每次取最大的给sum
				b[x][y] = max(b[x][y], sum);//记录最大的步数
			}
		}
	}
	return b[x][y];
}
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; i++)
	{
		for (int j = 1; j <= c; j++)
			dfs(i, j, 0);//步数一上来从0开始
	}
	for (int i = 1; i <= r; i++)
	{
		for (int j = 1; j <= c; j++)
		{
			tns = max(tns, b[i][j]);//找最大步数
		}
	}
	cout << tns;
	return 0;
}
```cpp
2021/4/6 17:26
加载中...