Poj-1088(记忆化搜索、DFS)

　

poj

点击打开问题链接

问题：

给出一个R行C列的二维数组表， 求出这个表中的最长递增序列的长度，只能上下左右相邻。

Sample Input

5 5
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

Sample Output

25

错误：

一开始直接普通的深搜，每一个点都深搜一遍，找出最大的。不出意料是超时的。

正解：

记忆化搜索，依然是深搜，但是用一个数组 来记录已经搜索过的点 且以这个点为起点的 最长递增序列 的长度，

这样下一次搜索到这个点的时候就直接返回长度就行，避免了重复的搜索。。。

#include <iOStream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN = 105;
int R,C;
int M[MAXN][MAXN];
int mark_len[MAXN][MAXN];

void init();
void get_map(int R, int C);
int DFS(int x, int y);

int main()
{   
    int max_len = 0;

    cin >> R >> C;
    init();
    get_map(R, C);
    for(int i = 0;i < R;i++)
    {
        for (int j = 0; j < C; j++)
        {
            max_len = max(max_len,DFS(i,j));
        }
    }
    
    cout << max_len << endl;
    system("pause");
    return 0;
}

void init()
{
    memset(M, 0, sizeof(M));
    memset(mark_len,0,sizeof(mark_len));
}

void get_map(int R, int C)
{
    
    for(int i = 0;i < R;i++)
    {
        for (int j = 0; j < C;j ++)
        {
            cin >> M[i][j];
        } 
    }
}

int DFS(int x, int y)
{
    // 记忆化搜索
    if(mark_len[x][y] != 0)
        return mark_len[x][y];

    int len = 1;
    int next[4][2] = {{0, 1},{1, 0},{0,-1},{-1,0}}; // 方向数组
    for (int i = 0; i < 4; i++)
    {
        int nx = x + next[i][0];
        int ny = y + next[i][1];
        if(nx < 0 || ny < 0 || nx == R || ny == C)
            continue;
        else if(M[nx][ny] > M[x][y])
        {
            // 这里想了好久才想明白，但是只能意会啊
             len = max(len, DFS(nx,ny)+1);
        }
    }
    // 记忆化搜索
    mark_len[x][y] = len;
    return len;
}

文章最后发布于: 2018-05-25 14:22:29

相关阅读

大奖章 量化 数据 接口

1. 股票历史数据、行情数据、券商交易接口2.免费的个人版3.支持多种语言：Matlab、R语言、Python、Excel/VBA、C++、C#6.模拟交易柜

运维——自动化安装系统（自制引导光盘及U盘启动）（二）

实现自动化安装操作系统我们仍需要插入光盘来引导，现在很多服务器已经没有光驱，那么此时我们就无法用光盘引导，如果要实现光盘引导安

无线淘宝成交转化率怎么提高？这三点决定了90%！

现在买家趋向于使用手机进行浏览购物，手机端和电脑端的转化率不一样，所以想要提高无线端的成交转化率，就需要掌握一些重点，那么具体怎

游戏化定义及表现形式：「游戏化」的 6 种常见元素

今天分享的这篇文章，将带你认识「游戏化」的 6 种常见元素。读完你才发现：手机里的 app 这么好玩，原来都用了这个设计技巧。如今的产

新站怎样优化让关键词获得更好的排名？看完这篇你就懂了

对于新站而言，网站关键词想要出现排名一般需要3个月左右的时间甚至更长时间，那么，如何优化新站，让关键词获得更好的网站排名?使网站排