[蓝桥杯2022省赛] X 图形

X 图形

问题描述

给定一个字母矩阵。一个?X?图形由中心点和由中心点向四个?4545?度斜线方向引出的直线段组成，四条线段的长度相同，而且四条线段上的字母和中心点的字母相同。

一个?X?图形可以使用三个整数r,c,L?来描述，其中 r,c?表示中心点位于第?r?行第 c?列，正整数?L?表示引出的直线段的长度。 对于?1?到?L?之间的每个整数?i，X?图形满足：第r?i?行第 c?i?列与第?r?行第?c?列相同，第 r?i?行第c+i?列与第?r?行第?c?列相同，第 r+i?行第 c?i?列与第?r?行第?c?列相同，第 r+i?行第 c+i?列与第?r?行第?c?列相同。

例如，对于下面的字母矩阵中，所有的字母?L?组成一个 X图形，中间的?5?个?L?也组成一个?X?图形。所有字母?Q?组成了一个?X?图形。

给定一个字母矩阵，请求其中有多少个?X?图形。

输入格式

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

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

输出格式

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

样例输入

5 6
LAAALA
ALQLQA
AALQAA
ALQLQA
LAAALA

样例输出

3

评测用例规模与约定

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

对于所有评测用例，1 <= n, m <= 100。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

总通过次数: 455??|??总提交次数: 589??|??通过率: 77.2%

代码分享：

#include <iostream>
using namespace std;
int main()
{
  int n,m,sum=0;
  cin>>n>>m;
  char s[101][101];
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      cin>>s[i][j];
    }
  }//字母矩阵的输入，i表示行，j表示列
  for(int i=1;i<n-1;i++){
    for(int j=1;j<m-1;j++){
            char w=s[i][j];//w表示中心点字符
            int k=1;
        //k用来表示与中心点的距离
        while(w==s[i-k][j-k]&&w==s[i-k][j+k]&&w==s[i+k][j-k]&&w==s[i+k][j+k]){
          sum++;
          k++;
        }
      }
    }
  cout<<sum;//输出最终找到的X的个数
  return 0;
}//代码由CDDN博主鑫鑫向栄分享