首页 > 其他分享 >OpenJ_Bailian - 1088

OpenJ_Bailian - 1088

时间:2023-01-11 23:01:58浏览次数:59  
标签:sy sx const OpenJ int 1088 110 Bailian dis

OpenJ_Bailian - 1088

题解:DFS记忆化搜索

记忆化搜索也可以说是动态规划,最后的答案也是从一个个子问题推导而来

#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10;
int n, m;
int g[110][110];
int dis[110][110]; // dis[x][y]代表从坐标(x,y)的点出发的最长路径
int vis[110][110];
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int dfs(int sx, int sy)
{
    if (dis[sx][sy])
        return dis[sx][sy];
    dis[sx][sy] = 1;
    for (int i = 0; i < 4; ++i)
    {
        int nx = sx + dir[i][0];
        int ny = sy + dir[i][1];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && g[nx][ny] < g[sx][sy])
        {
            vis[nx][ny] = 1;
            dis[sx][sy] = max(dfs(nx, ny) + 1, dis[sx][sy]);
            vis[nx][ny] = 0;
        }
    }
    return dis[sx][sy];
}
int main(void)
{
    Zeoy;
    int t = 1;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                cin >> g[i][j];
        int ans = -inf;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                ans = max(dfs(i, j), ans);
            }
        }
        cout << ans << endl;
    }
    return 0;
}

标签:sy,sx,const,OpenJ,int,1088,110,Bailian,dis
From: https://www.cnblogs.com/Zeoy-kkk/p/17045140.html

相关文章

  • OpenJ_Bailian - 1751
    OpenJ_Bailian-1751题解:最小生成树问题,Kruskal算法已经帮你建好的边就不用再建了,直接合并,当然我们这一题需要将给的坐标转化成边的,然后我们如何输出建哪几条路呢?我们......
  • CF1088C
    Solution一个很简单的想法就是将整个序列变成\(1\)到\(n\),这时我们需要对每个\(a_i\)执行\(\bmod(a_i-i)\)的操作,但是可能\(a_i<i\),所以我们只需要在一开始加上......
  • POJ-1088 滑雪
    POJ-1088滑雪有一个平面区域,上面有一些点,每个点对应一定的权值,每次移动只能从当前位置向上下左右四个方向中,权值小于当前位置权值的点移动,一次性最多可以移动多远(相邻位......
  • OpenJudge 1.8.11 图像旋转
    11:图像旋转总时间限制:1000ms内存限制:65536kB描述输入一个n行m列的黑白图像,将它顺时针旋转90度后输出。输入第一行包含两个整数n和m,表示图像包含像素点的行数和......
  • Centos7 卸载自带的OpenJDK
    一、查询系统是否已经安装jdkrpm-qa|grepjava二、卸载已安装的jdkrpm-e--nodepsjava-1.8.0-openjdk-1.8.0.181-7.b13.el7.x86_64rpm-e--nodepsjava-1.8.0-open......
  • 毕昇JDK团队主导的RISC-V port正式合入OpenJDK主线
    编者按:2022年3月14日,华为毕昇JDK团队主导开发的OpenJDKRISC-Vport[1]正式合入OpenJDK主线[2],成为OpenJDK的官方port之一。OpenJDK19将会是第一个支持......
  • 洛谷 P1088 火星人(乱搞)
    题目大意:已知有一串数字,问在原来的数字串的字典序加m后,应该输出多少解题思路:最简便的做法是用next_permutation,这个生成的全排列可以按照字典序递增,这里我用的是搜索的方法......
  • 永嘉微电/VINKA原厂-VK1088B是超小体积LCD液晶段码屏显示驱动IC-22*4点 小体积1621,4*4
    产品品牌:永嘉微电/VINKA产品型号:VK1088B封装形式:QFN32(4MM*4MM)概述:VK1088B是一个点阵式存储映射的LCD驱动器,可支持最大88点(22SEGx4COM)的LCD屏,也支持2COM和3COM的LCD屏......
  • OpenJudge 1.8.9 矩阵乘法
    09:矩阵乘法总时间限制:1000ms内存限制:65536kB描述计算两个矩阵的乘法。nm阶的矩阵A乘以mk阶的矩阵B得到的矩阵C是nk阶的,且C[i][j]=A[i][0]B[0][j]+A[i][1]B[1......
  • openjdk 8 alpine 镜像修改
    alpine镜像软件源修改为国内的修改时区为国内安装字体FROMopenjdk:8-alpineENVLANGen_US.UTF-8RUNsed-i's/dl-cdn.alpinelinux.org/mirrors.tuna.tsinghua.......