题解：P12242 [蓝桥杯 2023 国研究生组] 钉板上的正方形

· · 题解

写蓝题绿题题解没过，愤恨恨来写黄题题解我没不信过不了了。

前记：本人在一开始算的时候没考虑到部分方块，截止目前，有三分之一是我提交的了。

题意：

本题给了我们一个钉板，要我们算出一共有多少个大小不一的正方形。

为了方便处理，我们可以把钉板存入数组中。

为了方便，我们设 n = 10，也就是顶板的大小。

const int s[10][10] = {
    {1,1,0,1,0,1,1,1,1,1},
    {1,1,1,0,0,1,1,1,1,0},
    {1,1,0,0,1,0,1,1,1,1},
    {1,0,1,1,0,1,1,1,1,0},
    {1,0,1,0,1,1,1,1,0,0},
    {1,0,0,1,0,1,0,1,0,1},
    {1,1,1,1,1,1,1,1,1,0},
    {0,1,1,1,1,1,1,1,1,0},
    {0,1,1,0,1,0,1,1,1,1},
    {1,0,1,0,0,1,0,1,0,0}
    // 1就是有钉子，0就是没有
};

思路：

思路 1.0：

可以发现，这个钉板只有 10 \times 10 的大小。

于是我们可以手算，然后提交答案。

时间复杂度 O(1)。

思路 2.0：

什么？要手算？我从来不手算。

但是手算有点麻烦，我们可以用编程来计算。

枚举每个顶点，然后判断 4 个角是不是都有钉子。

然后统计答案。

时间复杂度 O(n ^ 4)。

思路 3.0：

然而枚举四个角不但浪费了很多时间，还有很多本身就不是一个正方形的，这个时候要怎么办？

我们可以换一种思路，枚举正方形的每条边，然后枚举当前的位置，判断四个角有没有顶点，有的话更新一下答案。

时间复杂度 O(n ^ 3)。

最终在各种思路的推算下，得出答案为 21。

虽然这道题思路 1 和 2 就可以过了，但是我们还是进行了优化，尽管没有任何意义，但是也可以提升一下思维，说不定在以后就有的能用得上呢。