思路：枚举+trick

这道题首先我们发现只要固定正方形两条相邻边，就可以得到这个正方形的具体信息。 但是直接固定两条边需要枚举三个点，复杂度比较高。

我们完全可以枚举一条边，然后将这条边顺时针或者逆时针旋转90度，从而实现固定两条边。这样只需要枚举两个点即可。

然后一个正方形按照这样的寻找策略会被找到4次，因此最后答案要除4。

时间复杂度：$O(n^2 m^2)$

代码

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> mp(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mp[i][j];
        }
    }

    int ans = 0;
    for (int x1 = 0; x1 < n; x1++) {
        for (int y1 = 0; y1 < m; y1++) {
            if (mp[x1][y1] == 'X') {
                for (int x2 = 0; x2 < n; x2++) {
                    for (int y2 = 0; y2 < m; y2++) {
                        if (x2 == x1 && y2 == y1) continue;
                        if (mp[x2][y2] == 'X') {
                            int dx = x2 - x1;
                            int dy = y2 - y1; // 按照向量顺时针或者逆时针
                            int x3 = x1 - dy; // 求到第三第四个点
                            int y3 = y1 + dx;
                            int x4 = x3 + dx;
                            int y4 = y3 + dy;
                            if (0 <= x3 && x3 < n && 0 <= y3 && y3 < m && 0 <= x4 && x4 < n && 0 <= y4 && y4 < m && mp[x3][y3] == 'X' && mp[x4][y4] == 'X') {
                                ans++; // 符合要求就计数
                            }
                        }
                    }
                }
            }
        }
    }

    cout << ans / 4 << "\n"; // 答案数除4

    return 0;
}

python

n, m = map(int, input().split())
mp = [list(input()) for i in range(n)]
ans = 0
for x1 in range(n):
    for y1 in range(m):
        if mp[x1][y1] == 'X':
            for x2 in range(n):
                for y2 in range(m):
                    if x2 == x1 and y2 == y1:continue
                    if mp[x2][y2] == 'X':
                        dx = x2 - x1
                        dy = y2 - y1 # 按照向量顺时针或者逆时针
                        x3, y3 = x1 - dy, y1 + dx # 求到第三第四个点
                        x4, y4 = x3 + dx, y3 + dy
                        if 0 <= x3 < n and 0 <= y3 < m and 0 <= x4 < n and 0 <= y4 < m and mp[x3][y3] == 'X' and mp[x4][y4] == 'X':
                            ans += 1 # 符合要求就计数
print(ans // 4) # 答案数除4

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        char[][] mp = new char[n][m];
        for (int i = 0; i < n; i++) {
            String line = scanner.next();
            for (int j = 0; j < m; j++) {
                mp[i][j] = line.charAt(j);
            }
        }

        int ans = 0;
        for (int x1 = 0; x1 < n; x1++) {
            for (int y1 = 0; y1 < m; y1++) {
                if (mp[x1][y1] == 'X') {
                    for (int x2 = 0; x2 < n; x2++) {
                        for (int y2 = 0; y2 < m; y2++) {
                            if (x2 == x1 && y2 == y1) {
                                continue;
                            }
                            if (mp[x2][y2] == 'X') {
                                int dx = x2 - x1;
                                int dy = y2 - y1; // 按照向量顺时针或者逆时针
                                int x3 = x1 - dy; // 求到第三第四个点
                                int y3 = y1 + dx;
                                int x4 = x3 + dx;
                                int y4 = y3 + dy;
                                if (0 <= x3 && x3 < n && 0 <= y3 && y3 < m && 0 <= x4 && x4 < n && 0 <= y4 && y4 < m && mp[x3][y3] == 'X' && mp[x4][y4] == 'X') {
                                    ans++; // 符合要求就计数
                                }
                            }
                        }
                    }
                }
            }
        }

        System.out.println(ans / 4); // 答案数除4
    }
}

题目内容

小红喜欢玩王者，尤其擅长奕星，并且时常沉迷于用奕星的大招困住敌人。

所以他设计了一个巨大棋局，棋盘中的格子只有两种可能，如果是 $'X'$ 则表示这个格子可以作为棋盘的一个边角，如果是 $'.'$ 则表示不可以。

小红要按这个棋局的情况去进行奕星的大招练习，即选择四个为 $'X'$ 的不同格子，这四个格子可以构成一个正方形棋盘。

现在小红想问你，可以获得多少个不同的正方形棋盘。

两个棋盘相同当且仅当四个边角都可以完全对应上，否则就是不同的正方形棋盘。

输入描述

第一行，一个正整数$n,m$，代表巨大棋局的大小

接下来$n$行，每行一个长度为$m$的字符串，仅包含$'.'$和$'X'$。

$1 \leq n,m \leq 50$

输出描述

一个整数，表示可以获得的不同棋盘的数量。

样例

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

4 4
XX.X
XX.X
.X.X
..X.

输出

2

说明 第一个正方形棋盘为:$(1,2),(3,2),(1,4),(3,4)$

第二个正方形棋盘为:$(1,1),(1,2),(2,1),(2,2)$