京东 · 穷举 · 算法编程题
京东 穷举 n ≤ 50 时限 1 秒 / 256 MB

题目描述

小红有一个大小为 n × m 的棋盘，'.' 表示这个格子没有棋子，'X' 表示这个格子有棋子。
第 i 行第 j 列的格子可以用一个坐标 (i, j) 表示。
小红想选出四个棋子，对应坐标分别为 (x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4) ，使得这四个坐标构成一个正方形，小红有多少种方案。
如果两个方案有任意一个棋子的坐标不同，那么就认为是两种不同的方案。

输入输出

输入描述
第一行一个正整数 n, m ，代表棋盘的大小。
接下来 n 行，每行一个长度为 m 的字符串，仅包含 '.' 和 'X'。
1≤ n, m ≤ 50
输出描述
一个整数，代表最终的方案数

样例共 1 组

样例 1 · 第一个正方形：(1, 1) (1, 2) (2, 1) (2, 2) 第二个正方形：(2, 3) (3, 2) (3, 4) (4, 3) 第三个正方形：(1, 2) (2, 1) (2, 3) (3, 2)
输入
4 4
XX..
XXX.
.X.X
..X.
输出
3

算法解析依据充分

考点：穷举 · 计算几何

数据规模 n ≤ 50 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 50，m ≤ 50
  • 复杂度门槛：允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：穷举

把候选答案空间全部列出来逐一检验，靠数据范围小来兜底。

思路框架（穷举 通法 · 非本题专属）

  1. 确定枚举什么（下标区间 / 子集 / 数值）。
  2. 用一层或多层循环（或递归）生成所有候选。
  3. 对每个候选判断是否满足题目条件，满足就统计或更新最优值。
  4. 先按数据范围估算枚举量，确认不会超时。

实现要点：多重循环是最直接的写法；枚举组合时可用递归 + 回溯，或用位掩码代表子集。

复杂度：时间 O(候选数 × 单次校验代价) ｜ 空间 O(1)

该范式的通法易错点

  • 没先估复杂度，枚举量超出时限（这是最常见的超时原因）。
  • 去重没做好，同一种方案被多次统计。

对照本题

  • 数据规模 n ≤ 50，允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。

样例解读

样例 1：输入 4 4 / XX.. / XXX. / .X.X / ..X. → 输出 3

第一个正方形：(1, 1) (1, 2) (2, 1) (2, 2)

第二个正方形：(2, 3) (3, 2) (3, 4) (4, 3)

第三个正方形：(1, 2) (2, 1) (2, 3) (3, 2)

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2023年秋招-京东-技术通用岗位-第一批笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解