A38891. 全相等三角形给定一个字母矩阵，定义一个LQ三角形为某行中连续的几个字母、某列中连续的几个字母和一条45度的斜线中连续的几个字母组成的等腰直角三角形的边缘部分，其中每条边上的字母数量相等且至少为2。例如，对于下面的字母矩阵中，所有的字母L组成一个LQ三角形，所有字母Q组成了一个LQ三角形，所有字母C也组成了一个LQ三角形。如果一个LQ三角形边上的所有字母相等，则称为一个全相等三角形。以三个例子都是…
填空题
困难
知识点
题目描述
全相等三角形
给定一个字母矩阵，定义一个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。
参考答案
#初始化矩阵
n,m=map(int,input().split())
mp = []
for _ in range(n):
mp.append(list(input()))
def rt_down(i,j,l): #右下是否构成全相等三角形
if j+l-1>=m or i+l-1>=n: #越界
return False
x, y = i, j
for k in range(l): #向右直线
if mp[i][j]!=mp[x][y]:
return False
y+=1
x, y = i, j
for k in range(l):#向下直线
if mp[i][j] != mp[x][y]:
return False
x+=1
x, y = i, j+l-1
for k in range(l) :#右->左下 斜线
if mp[i][j] != mp[x][y]:
return False
x+=1
y-=1
return True
def lf_down(i,j,l): #左下是否构成全相等三角形
if j-l+1<0 or i+l-1>=n:#越界
return False
x, y = i, j
for k in range(l) :#向左直线
if mp[i][j]!=mp[x][y]:
return False
y-=1
x, y = i, j
for k in range(l):#向下直线
if mp[i][j] != mp[x][y]:
return False
x+=1
x, y = i, j-l+1
for k in range(l):#左->右下 斜线
if mp[i][j] != mp[x][y]:
return False
x+=1
y+=1
return True
def lf_up(i,j,l):#左上是否构成全相等三角形
if j-l+1<0 or i-l+1<0 :#越界
return False
x, y = i, j
for k in range(l) :#向左直线
if mp[i][j]!=mp[x][y]:
return False
y-=1
x, y = i, j
for k in range(l) :#向上直线
if mp[i][j] != mp[x][y]:
return False
x-=1
x, y = i-l+1, j
for k in range(l):#上->左下 斜线
if mp[i][j] != mp[x][y]:
return False
x+=1
y-=1
return True
def rt_up(i,j,l):#右上是否构成全相等三角形
if j+l-1>=m or i-l+1<0 :#越界
return False
x, y = i, j
for k in range(l) :#向右直线
if mp[i][j]!=mp[x][y]:
return False
y+=1
x, y = i, j
for k in range(l) :#向上直线
if mp[i][j] != mp[x][y]:
return False
x-=1
x, y = i-l+1, j
for k in range(l):#上->左下 斜线
if mp[i][j] != mp[x][y]:
return False
x+=1
y+=1
return True
l=min(n,m)
ans=0
for k in range(2,l+1):
for i in range(n):
for j in range(m): #向四个方向查看边长为k的全相等三角形
if rt_down(i,j,k):
ans+=1
if lf_down(i,j,k):
ans+=1
if lf_up(i,j,k):
ans+=1
if rt_up(i,j,k):
ans+=1
print(ans)
上一题
下一题