【问题描述】

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


例如,对于下面的字母矩阵中,所有的字母 L 组成一个LQ三角形,所有字母 Q 组成了一个 LQ 三角形,所有字母 C 也组成了一个 LQ 三角形。
AAAAAAA ALLLLLA ALQQLAA ALQLAAC ALLAACC ALAACCC
如果一个 LQ 三角形边上的所有字母相等,则称为一个全相等三角形。以三个例子都是全相等三角形。

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

【输入格式】

输入第一行包含两个整数 n, m,分别表示字母矩阵的行数和列数。
接下来 n 行,每行 m 个大写字母,为给定的矩阵。

【输出格式】

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

【样例输入】
3 4 AAAA ALAQ ALQQ
【样例输出】
4
【样例输入】
6 7 AAAAAAA ALLLLLA ALQQLAA ALQLAAC ALLAACC ALAACCC
【样例输出】
23
题解:枚举
#include <bits/stdc++.h> using namespace std; const int N = 15; int n, m; int
len; int ans = 0; string a[N]; bool check(int i, int j, int di, int dj) { char c
= a[i][j]; for(int k = 0; k < len - 1; k++) { i += di; j += dj; if(i < 0 || i >=
n|| j < 0 || j >= m) return false; if(c != a[i][j]) return false; } return true
; } int main() { cin >> n >> m; for(int i = 0; i < n; i++) { cin >> a[i]; } for(
len= min(n, m); len >= 2; len--) { for(int i = 0; i < n; i++) { for(int j = 0; j
< m; j++) { ans += (check(i, j, 1, 0) && check(i, j, 0, 1) && check(i + len - 1,
j, -1, 1)); ans += (check(i, j, 1, 0) && check(i, j, 0, -1) && check(i + len -
1, j, -1, -1)); ans += (check(i, j, -1, 0) && check(i, j, 0, 1) && check(i - len
+ 1, j, 1, 1)); ans += (check(i, j, -1, 0) && check(i, j, 0, -1) && check(i -
len+ 1, j, 1, -1)); } } } cout << ans << endl; return 0; }

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信