矩阵全相等三角形——枚举

问题描述
　　给定一个字母矩阵，定义一个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
评测用例规模与约定
　　对于 50% 的评测用例，1 <= n, m <= 10。
　　对于所有评测用例，1 <= n, m <= 100。

分析

三角形直边与斜边上的字符个数相同，且字符也一样，直接枚举三角形边长，然后两层for枚举顶点，分别判断该顶点位于左上角、右上角、左下角、右下角的四种情况；从顶点出发，分别向右水平走、向下水平走、斜着走，然后通过函数去判断是不是字符都相等即可；

import java.util.Scanner;

public class Main {
    static char a[][] = new char[105][105];
    static int len, n, m;

    static boolean check(int i, int j, int directi, int directj) {
        if (i <= 0 || j <= 0 || i > n || j > m)
            return false;
        char ch = a[i][j];
        //判断从(i,j)开始，方向为directi,directj
        for (int k = 0; k < len - 1; k++) {
            i = i + directi;
            j = j + directj;
            if (i <= 0 || j <= 0 || i > n || j > m)
                return false;
            if (a[i][j] != ch)
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            String s = sc.next();
            char[] ch = s.toCharArray();
            for (int j = 0; j < ch.length; j++) {
                a[i][j + 1] = ch[j];
            }
        }
        int ans = 0;
        //枚举边长
        for (len = 2; len <= Math.min(n, m); len++) {
            //枚举三角形的顶点
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    //顶点在左上，分别向右、向下、从(i,j+len-1)开始的右上到左下的对角线
                    if (check(i, j, 0, 1) && check(i, j, 1, 0) && check(i, j + len - 1, 1, -1))
                        ans++;
                    //顶点在右上
                    if (check(i, j, 0, -1) && check(i, j, 1, 0) && check(i, j - len + 1, 1, 1))
                        ans++;
                    //顶点在左下
                    if (check(i, j, -1, 0) && check(i, j, 0, 1) && check(i - len + 1, j, 1, 1))
                        ans++;
                    //顶点在右下
                    if (check(i, j, -1, 0) && check(i, j, 0, -1) && check(i - len + 1, j, 1, -1))
                        ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58