蓝桥杯 2024 省赛 Python B 连连看题目详解与题解

暴力思路

首先想到的肯定是这种思路：枚举每组点对，判断其是否满足题目中的两个要求。

时间复杂度： $O(n^4)$ 。但看一下数据范围： $n \le 1000$ ，不用说是过不了的。

AC思路

我们先观察一下条件：第一条是 $|a-c| = |b-d| > 0$ ，其要求大于零表示该点对的点不能是同一个点。还有要求横坐标之差等于纵坐标之差，我们可以发现：满足该要求的点对必然是某一正方形的其中一对对角。所以我们可以不断构造这样的点对，只要判断一下点对上的两个数是否相等。具体操作方法如下：

1. 选定一个点，作为点对中的一个点。
2. 将选定的点的横坐标与纵坐标加减同样的值得出另外一个点的坐标，于是这两个点的坐标必定满足条件一： $|a-c| = |b-d| > 0$ 。
3. 判断这两个点是否满足条件二：两点上的值相等，如果满足条件，将答案累加。

注意

点对 $(a,b)$ 和 $(c,d)$ 与另外一个点对 $(c,d)$ 和 $(a,b)$ 是两个不同的点对。

该做法时间复杂度： $O(n^3)$ 。因为时限是两秒，所以还是可以过的。

于是我们得出了下面的代码（先别急，这份代码过不了）：

#include<bits/stdc++.h>

using namespace std;

int n,m,a[1005][1005],ans;

int main()
{
    
    cin>>n>>m;
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    
  
    //两个点，一个在左上，一个在右下的情况：
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
        {
            int x=i+1,y=j+1;
            //将选定的点的横坐标与纵坐标加上同样的值得出另外一个点的坐标
            for(;x<=n&&y<=m;x++,y++)
            {
                if(a[x][y]==a[i][j])//判定是否相等 
                    ans++;
            }
        }
    
    //两个点，一个在右上，一个在左下的情况：
    for(int i=1;i<n;i++)
        for(int j=m;j>1;j--)
        {
            int x=i+1,y=j-1;
            //将选定的点的横坐标与纵坐标加减同样的值得出另外一个点的坐标
            for(;x<=n&&y>=1;x++,y--)
            {
                if(a[x][y]==a[i][j])//判定是否相等 
                    ans++;
            }
        }
    
    cout<<ans*2;//每种点对倒过来，又是另一种点对，所以乘2
    
    return 0;
}

这份代码如果提交，会TLE两个点，所以得优化一下。
我们不妨把