刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

全相等三角形

给定一个字母矩阵,定义一个LQ三角形为某行中连续的几个字母、某列中连续的几个字母和一条45度的斜线中连续的几个字母组成的等腰直角三角形的边缘部分,其中每条边上的字母数量相等且至少为2。

例如,对于下面的字母矩阵中,所有的字母L组成一个LQ三角形,所有字母Q组成了一个LQ三角形,所有字母C也组成了一个LQ三角形。

如果一个LQ三角形边上的所有字母相等,则称为一个全相等三角形。以三个例子都是全相等三角形。

给定一个字母矩阵,请求其中有多少个全相等三角形。

输入格式

输入第一行包含两个整数n,m,分别表示字母矩阵的行数和列数。

接下来n行,每行m个大写字母,为给定的矩阵。

输出格式

输出一行,包含一个整数,表示答案。


样例输入1

3 4
AAAA
ALAQ
ALQQ

样例输出1

4


样例输入2

6 7
AAAAAAA
ALLLLLA
ALQQLAA
ALQLAAC
ALLAACC
ALAACCC

样例输出2

23

评测用例规模与约定

对于50%的评测用例,1<=n,m<=10。对于所有评测用例,1<=n,m<=100。

使用微信搜索喵呜刷题,轻松应对考试!

答案:

这道题是一道求解全相等三角形数量的算法题。可以使用动态规划来解决这个问题。首先,我们可以定义一个三维数组dp[i][j][k],其中i表示当前行,j表示当前列,k表示当前斜线。dp[i][j][k]表示以(i,j)为右下角的全相等三角形的数量。然后,我们可以使用动态规划的思想,从第一行开始,逐行计算dp数组。对于每一行,我们可以遍历所有的列和斜线,判断当前位置是否能够构成一个全相等三角形。如果可以,则更新dp数组。具体判断条件是:如果当前位置的字母和它的上方、左方、左上方三个位置的字母相等,则可以构成一个全相等三角形。此时,我们需要分别计算以当前位置为右下角的行三角形、列三角形和斜三角形的数量,并将它们累加到dp数组中。最后,输出dp[n][m][k]的最大值即可。

解析:

【喵呜刷题小喵解析】:
这个题目的主要难度在于如何判断当前位置是否能够构成一个全相等三角形,并且如何计算三角形的数量。由于需要同时考虑行、列和斜线三个方向,所以需要使用三维数组来记录状态。动态规划的思想可以帮助我们逐行计算dp数组,从而避免重复计算。在判断当前位置是否能够构成一个全相等三角形时,需要同时考虑当前位置的字母和它的上方、左方、左上方三个位置的字母是否相等。如果可以构成一个全相等三角形,则需要分别计算以当前位置为右下角的行三角形、列三角形和斜三角形的数量,并将它们累加到dp数组中。在计算三角形数量时,需要根据三角形的不同类型,使用不同的计算公式。最后,输出dp数组中的最大值即可得到答案。
创作类型:
原创

本文链接:全相等三角形 给定一个字母矩阵,定义一个LQ三角形为某行中连续的几个字母、某列中连续的几个字母和一条

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share