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博主鑫鑫向栄分享