第十四届蓝桥杯模拟赛c++ 试题 I

【问题描述】

给定一个字母矩阵，定义一个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; }

• « 上一篇：李峋爱心代码
• » 下一篇：6.7 数据结构——最短路径