题解 | #小红的棋盘#

题目链接

小红的棋盘

题目描述

小红有一个大小为 $n \times m$ 的棋盘，'.' 表示这个格子没有棋子，'X' 表示这个格子有棋子。

小红想选出四个棋子，使得这四个棋子的坐标构成一个正方形。

问小红有多少种选择方案。如果两个方案有任意一个棋子的坐标不同，那么就认为是两种不同的方案。

解题思路

1. 核心思想

问题的核心是在 $n \times m$ 的点阵中寻找由四个 'X' 构成的正方形。由于 $n, m$ 的范围（ $n, m \le 50$ ）不大，我们可以设计一个多项式时间复杂度的暴力枚举算法。

直接枚举四个点并判断是否构成正方形的复杂度过高。一个更高效的策略是：枚举两个点，然后计算出另外两个点的位置。

2. 算法设计

我们可以遍历棋盘上所有有序的点对 $(A, B)$ ，其中 $A$ 和 $B$ 的位置上都必须是棋子 'X'。对于每一个点对，我们假设它们是正方形的一条边。

令点 $A$ 的坐标为 $(r_1, c_1)$ ，点 $B$ 的坐标为 $(r_2, c_2)$ 。
从 $A$ 指向 $B$ 的向量可以表示为 $\vec{AB} = (dr, dc) = (r_2 - r_1, c_2 - c_1)$ 。
一个正方形的另外两个顶点 $C$ 和 $D$ 可以通过将向量 $\vec{AB}$ 旋转 $90^\circ$ 得到。
一个二维向量 $(dx, dy)$ 逆时针旋转 $90^\circ$ 后会变为 $(-dy, dx)$ 。
因此，我们可以找到另外两个顶点 $D$ 和 $C$ 的坐标：
- 点 $D$ 是由点 $A$ 沿着与 $\vec{AB}$ 垂直且等长的方向移动得到： $D = A + \text{rotate}_{90}(\vec{AB}) = (r_1, c_1) + (-dc, dr) = (r_1 - dc, c_1 + dr)$ 。
- 点 $C$ 是由点 $B$ 沿同样方向移动得到： $C = B + \text{rotate}_{90}(\vec{AB}) = (r_2, c_2) + (-dc, dr) = (r_2 - dc, c_2 + dr)$ 。

基于此，我们可以构建以下算法：

初始化一个计数器 count 为 0。
使用四层循环，遍历所有可能的有序点对 $(A(r_1, c_1), B(r_2, c_2))$ 。
在循环中，首先检查 $grid[r_1][c_1]$ 和 $grid[r_2][c_2]$ 是否都为 'X'。
如果是，则根据上述公式计算出候选点 $C(r_3, c_3)$ 和 $D(r_4, c_4)$ 的坐标。
检查 $C$ 和 $D$ 的坐标是否在棋盘边界内（即 $0 \le r, c < N$ ）。
如果坐标有效，则进一步检查 $grid[r_3][c_3]$ 和 $grid[r_4][c_4]$ 是否也为 'X'。
如果所有四个点都存在，说明我们找到了一个正方形的“有向边”表示，将 count 加 1。

3. 重复计数问题

上述算法会重复计数。对于一个确定的正方形（例如，顶点为 $P_1, P_2, P_3, P_4$ ，按逆时针顺序），我们的算法会找到它多少次呢？

当我们枚举的 $(A, B)$ 是 $(P_1, P_2)$ 时，会找到 $(C, D) = (P_3, P_4)$ ，计数+1。
当我们枚举的 $(A, B)$ 是 $(P_2, P_1)$ 时，会找到 $(C, D) = (P_4, P_1)$ ，计数+1。
... 以此类推。

一个正方形有 4 条边，每条边可以构成 2 个方向相反的有序对（如 $(P_1, P_2)$ 和 $(P_2, P_1)$ ）。这 $4 \times 2 = 8$ 个有序对都会且仅会找到这同一个正方形。

因此，每个独特的正方形都被我们的算法精确地计数了 8 次。最终的答案应该是 count / 8。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }

    int count = 0;
    for (int r1 = 0; r1 < n; ++r1) {
        for (int c1 = 0; c1 < m; ++c1) {
            if (grid[r1][c1] == 'X') {
                for (int r2 = 0; r2 < n; ++r2) {
                    for (int c2 = 0; c2 < m; ++c2) {
                        if (r1 == r2 && c1 == c2) continue;
                        if (grid[r2][c2] == 'X') {
                            int dr = r2 - r1;
                            int dc = c2 - c1;

                            // Based on an ordered pair (A, B), calculate the other two points
                            // C and D assuming A-B is a side of a square in CCW order.
                            int r3 = r2 - dc;
                            int c3 = c2 + dr;
                            int r4 = r1 - dc;
                            int c4 = c1 + dr;

                            if (r3 >= 0 && r3 < n && c3 >= 0 && c3 < m &&
                                r4 >= 0 && r4 < n && c4 >= 0 && c4 < m) {
                                if (grid[r3][c3] == 'X' && grid[r4][c4] == 'X') {
                                    count++;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    // Each square has 4 vertices, let's say P1, P2, P3, P4 in CCW order.
    // Our formula will find the square for the following 4 ordered pairs (directed edges):
    // (P1, P2), (P2, P3), (P3, P4), (P4, P1).
    // The pairs in the opposite direction (e.g., (P2, P1)) will not find this square.
    // Thus, each unique square is counted exactly 4 times.
    cout << count / 4 << endl;

    return 0;
}

import java.util.Scanner;

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

        int count = 0;
        for (int r1 = 0; r1 < n; r1++) {
            for (int c1 = 0; c1 < m; c1++) {
                if (grid[r1][c1] == 'X') {
                    for (int r2 = 0; r2 < n; r2++) {
                        for (int c2 = 0; c2 < m; c2++) {
                            if (r1 == r2 && c1 == c2) continue;
                            if (grid[r2][c2] == 'X') {
                                int dr = r2 - r1;
                                int dc = c2 - c1;

                                // Based on an ordered pair (A, B), calculate the other two points
                                // C and D assuming A-B is a side of a square in CCW order.
                                int r3 = r2 - dc;
                                int c3 = c2 + dr;
                                int r4 = r1 - dc;
                                int c4 = c1 + dr;

                                if (r3 >= 0 && r3 < n && c3 >= 0 && c3 < m &&
                                    r4 >= 0 && r4 < n && c4 >= 0 && c4 < m) {
                                    if (grid[r3][c3] == 'X' && grid[r4][c4] == 'X') {
                                        count++;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        // Each square has 4 vertices, let's say P1, P2, P3, P4 in CCW order.
        // Our formula will find the square for the following 4 ordered pairs (directed edges):
        // (P1, P2), (P2, P3), (P3, P4), (P4, P1).
        // The pairs in the opposite direction (e.g., (P2, P1)) will not find this square.
        // Thus, each unique square is counted exactly 4 times.
        System.out.println(count / 4);
    }
}

import sys

def solve():
    try:
        line = sys.stdin.readline()
        if not line:
            return
        n, m = map(int, line.split())
        grid = [sys.stdin.readline().strip() for _ in range(n)]
    except (IOError, ValueError):
        return

    count = 0
    for r1 in range(n):
        for c1 in range(m):
            if grid[r1][c1] == 'X':
                for r2 in range(n):
                    for c2 in range(m):
                        if r1 == r2 and c1 == c2:
                            continue
                        
                        if grid[r2][c2] == 'X':
                            dr = r2 - r1
                            dc = c2 - c1
                            
                            # Based on an ordered pair (A, B), calculate the other two points
                            # C and D assuming A-B is a side of a square in CCW order.
                            r3 = r2 - dc
                            c3 = c2 + dr
                            r4 = r1 - dc
                            c4 = c1 + dr
                            
                            if 0 <= r3 < n and 0 <= c3 < m and \
                               0 <= r4 < n and 0 <= c4 < m:
                                if grid[r3][c3] == 'X' and grid[r4][c4] == 'X':
                                    count += 1
                                    
    # Each square has 4 vertices, let's say P1, P2, P3, P4 in CCW order.
    # Our formula will find the square for the following 4 ordered pairs (directed edges):
    # (P1, P2), (P2, P3), (P3, P4), (P4, P1).
    # The pairs in the opposite direction (e.g., (P2, P1)) will not find this square.
    # Thus, each unique square is counted exactly 4 times.
    print(count // 4)

solve()

算法及复杂度

算法：暴力枚举
时间复杂度： $O(N^2 \cdot M^2)$ 。
- 我们使用了四层嵌套循环来遍历棋盘上所有的有序点对 $(A, B)$ ，其中 $A$ 的坐标为 $(r_1, c_1)$ ，B 的坐标为 $(r_2, c_2)$ 。 $r_1, r_2$ 的范围是 $N$ ， $c_1, c_2$ 的范围是 $M$ 。内部的计算和检查都是 $O(1)$ 的操作。
空间复杂度： $O(N \cdot M)$ 。
- 主要的空间开销来自于存储输入的 $N \times M$ 棋盘。