题解：P11001 [蓝桥杯 2024 省 Python B] 连连看

JYX0924 · 2024-08-27 21:07:35 · 题解

这道题本质上是问有多少对 a_{x,y}=a_{x+i,y+i}。

对于每一条平行于对角线的线，我们可以用优先队列来存一下这条线上的每一个数。统计时假设 x 有 y 个，那么 x 对答案的贡献就是 y\times(y-1)。

下面是我的 AC 代码。

#include<bits/stdc++.h>
#define ll long long 
#define maxn 1005 
using namespace std;
ll n,m,a[maxn][maxn],vis[maxn][maxn],tot,ans;
priority_queue<ll> q[maxn<<2];
void dfs1(int row,int col)
{
    if(vis[row][col]==1||row>n||col>m||row<1||col<1) return;
    vis[row][col]=1; q[tot].push(a[row][col]);
    dfs1(row+1,col+1); dfs1(row-1,col-1);
}
void dfs2(int row,int col)
{
    if(vis[row][col]==2||row>n||col>m||row<1||col<1) return;
    vis[row][col]=2; q[tot].push(a[row][col]);
    dfs2(row-1,col+1); dfs2(row+1,col-1);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    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++)
    {
        if(vis[i][j]==1) continue;
        tot++; dfs1(i,j);
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
    {
        if(vis[i][j]==2) continue;
        tot++; dfs2(i,j);
    }
    for(int i=1;i<=tot;i++)
    {
        if(q[i].size()<=1) continue;
        while(!q[i].empty())
        {
            ll now=q[i].top(),num=1; q[i].pop();
            while(!q[i].empty()&&q[i].top()==now) q[i].pop(),num++;
            ans=ans+num*(num-1);
        }
    }
    cout<<ans;
    return 0;
}

谢谢大家！！！