首页 > 其他分享 >Monotonic Matrix (LVG引理, 路径不相交)

Monotonic Matrix (LVG引理, 路径不相交)

时间:2023-06-13 16:55:53浏览次数:38  
标签:方案 终点 Matrix 路径 矩阵 Monotonic 相交 LVG

引入

给定一个 n×m 的网格图,两个点从左下角出发,只能向上或者向右走,最后到右上角结束,求有多少种可能的方案,使得两个点的路径在除开起点和终点外的任意点不相交?

由于交换路径过后算同一种方案,我们就可以除开起点和终点,转换成A点从(1,2)出发到(m-1,n),B点从(2,1)出发到(m,n-1),再来统计不相交的路径方案数。

1.统计A、B独立地从各自起点走到各自终点的路径方案数,答案加上两者的乘积。

2.交换A、B的终点,再次统计方案数,答案减去两者乘积。

 

 题目大意:

一个矩阵由012三个数字组成,这个矩阵从左到右,从上到下,都是不递减的

思路:

  • 转化为2个路径, 把矩阵分成 0 1 2 ,3个部分
  • 这个路径是 坐上到右下的 
  • 然后 这个线可以相交的,  将其中一个线, 向左向下 平移一下即可
  • 然后2个点在矩阵中的路径 是可以通过组合数求出来的
  • 于是直接套 LVG定理即可

标签:方案,终点,Matrix,路径,矩阵,Monotonic,相交,LVG
From: https://www.cnblogs.com/Lamboofhome/p/17478116.html

相关文章

  • Codeforces Round #221 (Div. 2)-D. Maximum Submatrix 2
    原题链接D.MaximumSubmatrix2timelimitpertestmemorylimitpertestinputoutputYouaregivenamatrixconsistingofdigitszeroandone,itssizeis n × m.Youare......
  • Looksery Cup 2015-H. Degenerate Matrix(浮点数二分)
    原题链接H.DegenerateMatrixtimelimitpertestmemorylimitpertestinputoutputdeterminant ofamatrix 2 × 2degeneratenorm ||A|| ofamatrix AYouaregivenamatrix .Consideranydegeneratemat......
  • 利用arm cortex-m芯片 SIMD加速LVGL的文字渲染
    最近手上有个项目,对流畅度要求到极致。就是要满60fps的那种。所以针对各个模块的渲染都有一些改进。文字渲染加速就式其中之一。趁着记忆尤新把这个给记录下来SIMD介绍SIMD(单指令多数据)是一种计算机指令集架构,它允许处理器同时对多个数据元素执行相同的操作。这种指令集架构可......
  • 新的权限模型Matrix data access structure介绍
    这是我的第494篇原创文章,写于2023年6月8日。2021年11月2日,PowerApps博客的博文 AnnouncingPublicPreviewformodernizebusinessunits 宣布了ModernizedBusinessUnits开启Publicpreview阶段,到本文写作时,这个Feature已经GeneralAvailable了。相关功能介绍请参考官方文档......
  • [LeetCode] 1351. Count Negative Numbers in a Sorted Matrix
    Givena mxn matrix grid whichissortedinnon-increasingorderbothrow-wiseandcolumn-wise,return thenumberof negative numbersin grid.Example1:Input:grid=[[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]Output:8Explanation:Thereare......
  • leetcode 566. Reshape the Matrix
    InMATLAB,thereisaveryusefulfunctioncalled'reshape',whichcanreshapeamatrixintoanewonewithdifferentsizebutkeepitsoriginaldata.You'regivenamatrixrepresentedbyatwo-dimensionalarray,andtwopositiveintegersr......
  • leetcode 766. Toeplitz Matrix
    AmatrixisToeplitzifeverydiagonalfromtop-lefttobottom-righthasthesameelement.NowgivenanMxNmatrix,return True ifandonlyifthematrixisToeplitz. Example1:Input:matrix=[[1,2,3,4],[5,1,2,3],[9,5,1,2]]Output:TrueExplanation:12......
  • leetcode 378. Kth Smallest Element in a Sorted Matrix
    Givenanxnmatrixwhereeachoftherowsandcolumnsaresortedinascendingorder,findthekthsmallestelementinthematrix.Notethatitisthekthsmallestelementinthesortedorder,notthekthdistinctelement.Example:matrix=[[1,5,9......
  • 74. Search a 2D Matrix刷题笔记
    题目描述用了两个二分查找法。当然也可以把matrix转为数组来索引classSolution:defsearchMatrix(self,matrix:List[List[int]],target:int)->bool:low=0high=len(matrix)-1mid=0whilelow<=high:mid=(high......
  • as3 图像颜色渐变中使用matrix
    graphics 对象也可以绘制渐变笔触和填充,而不是纯色笔触和填充。渐变笔触是使用 lineGradientStyle() 方法创建的;渐变填充是使用 beginGradientFill() 方法创建的。 这两种方法接受相同的参数。前四个参数是必需的,即类型、颜色、Alpha 以及比率。其余四个参数是可选的,但对于......