小红的棋盘

[题目链接](https://www.nowcoder.com/practice/b4613aeaf115436394d87cf9db1098ca)

思路

给定一个 的棋盘，需要找出所有由 X 构成的正方形的方案数。注意正方形不限于轴对齐，可以是任意旋转角度的正方形。

核心思想：枚举边 + 旋转验证

一个正方形由四个顶点确定。如果我们枚举所有可能的四元组，复杂度为 （ 为棋子数），太高了。

更好的做法是枚举正方形的一条边。对于正方形的任意一条边 ，另外两个顶点的位置是唯一确定的——只需将向量 旋转 即可得到。

具体地，设两个棋子坐标为 和 ，令 ，，则：

  • 方向一（顺时针旋转 ）：另外两个顶点为 和
  • 方向二（逆时针旋转 ）：另外两个顶点为 和

去重

每个正方形有 4 条边，每条边恰好被枚举一次（因为我们只枚举无序对），所以每个正方形会被统计 4 次。最终答案除以 4 即可。

样例演示

XX..
XXX.
.X.X
..X.

棋子坐标集合：。

  • 枚举边 ：旋转后检查 均存在，计数 +1。
  • 枚举边 ：旋转后检查 均存在，计数 +1。
  • 枚举边 ：旋转后检查 均存在，计数 +1。
  • ......

最终总计数为 12，除以 4 得到答案 3。

复杂度分析

  • 时间复杂度：，其中 为棋子总数，枚举所有无序对。哈希集合查询为 。
  • 空间复杂度：，存储棋子坐标集合。

代码

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

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    vector<pair<int,int>> pts;
    set<pair<int,int>> st;
    for(int i = 0; i < n; i++){
        char buf[2010];
        scanf("%s", buf);
        for(int j = 0; j < m; j++){
            if(buf[j] == 'X'){
                pts.push_back({i, j});
                st.insert({i, j});
            }
        }
    }
    int ans = 0, sz = pts.size();
    for(int i = 0; i < sz; i++){
        for(int j = i+1; j < sz; j++){
            int x1 = pts[i].first, y1 = pts[i].second;
            int x2 = pts[j].first, y2 = pts[j].second;
            int dx = x2 - x1, dy = y2 - y1;
            if(st.count({x1+dy, y1-dx}) && st.count({x2+dy, y2-dx})) ans++;
            if(st.count({x1-dy, y1+dx}) && st.count({x2-dy, y2+dx})) ans++;
        }
    }
    printf("%d\n", ans / 4);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        boolean[][] grid = new boolean[n][m];
        List<int[]> pts = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            for (int j = 0; j < m; j++) {
                if (s.charAt(j) == 'X') {
                    grid[i][j] = true;
                    pts.add(new int[]{i, j});
                }
            }
        }
        int ans = 0, sz = pts.size();
        for (int i = 0; i < sz; i++) {
            for (int j = i + 1; j < sz; j++) {
                int x1 = pts.get(i)[0], y1 = pts.get(i)[1];
                int x2 = pts.get(j)[0], y2 = pts.get(j)[1];
                int dx = x2 - x1, dy = y2 - y1;
                int x3 = x1 + dy, y3 = y1 - dx, x4 = x2 + dy, y4 = y2 - dx;
                if (x3 >= 0 && x3 < n && y3 >= 0 && y3 < m &&
                    x4 >= 0 && x4 < n && y4 >= 0 && y4 < m &&
                    grid[x3][y3] && grid[x4][y4]) ans++;
                x3 = x1 - dy; y3 = y1 + dx; x4 = x2 - dy; y4 = y2 + dx;
                if (x3 >= 0 && x3 < n && y3 >= 0 && y3 < m &&
                    x4 >= 0 && x4 < n && y4 >= 0 && y4 < m &&
                    grid[x3][y3] && grid[x4][y4]) ans++;
            }
        }
        System.out.println(ans / 4);
    }
}

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    pts = []
    st = set()
    for i in range(n):
        s = input().strip()
        for j in range(len(s)):
            if s[j] == 'X':
                pts.append((i, j))
                st.add((i, j))
    ans = 0
    sz = len(pts)
    for i in range(sz):
        x1, y1 = pts[i]
        for j in range(i + 1, sz):
            x2, y2 = pts[j]
            dx, dy = x2 - x1, y2 - y1
            if (x1 + dy, y1 - dx) in st and (x2 + dy, y2 - dx) in st:
                ans += 1
            if (x1 - dy, y1 + dx) in st and (x2 - dy, y2 + dx) in st:
                ans += 1
    print(ans // 4)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const [n, m] = lines[0].split(' ').map(Number);
    const pts = [];
    const st = new Set();
    for (let i = 0; i < n; i++) {
        const s = lines[i + 1];
        for (let j = 0; j < s.length; j++) {
            if (s[j] === 'X') {
                pts.push([i, j]);
                st.add(i + ',' + j);
            }
        }
    }
    let ans = 0;
    const sz = pts.length;
    for (let i = 0; i < sz; i++) {
        const [x1, y1] = pts[i];
        for (let j = i + 1; j < sz; j++) {
            const [x2, y2] = pts[j];
            const dx = x2 - x1, dy = y2 - y1;
            if (st.has((x1+dy)+','+(y1-dx)) && st.has((x2+dy)+','+(y2-dx))) ans++;
            if (st.has((x1-dy)+','+(y1+dx)) && st.has((x2-dy)+','+(y2+dx))) ans++;
        }
    }
    console.log(Math.floor(ans / 4));
});