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

Breath_of_the_Wild · 2024-08-28 21:16:09 · 题解

使用一种跑起来非常非常慢的做法，但能 AC。

枚举每一个点 a_{i,j}，扫一遍 a_{i,j} 的右下方和左下方是否有与其相同的节点，相同则贡献 +1。（用 k 表示枚举到的节点和 a_{i,j} 横或纵坐标之差）

注意边界问题。可以每次循环判断当前节点是否越界，不过这样做较慢，不如提前算好 k 要从 1 循环到几。现在来考虑这个问题。如果从 a_{i,j} 往右下方扫，那么横坐标最多动 n-i，纵坐标最多动 m-j；如果从 a_{i,j} 往左下方扫，那么横坐标最多动 n-i，纵坐标最多动 m-j。每一种情况的 k 能扫到的最大值为横坐标与纵坐标最多动的格数的最小值。这些都是比较显然的。

那么为什么不把 a_{i,j} 的斜着 4 个方向都枚举一遍？显然太慢了，常数为上述的 2 倍，直接枚举两个不在同一条直线的方向即可。所以用上面的算法得到的结果乘 2 即为最终答案。

int main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
//  输入...
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int mn1=min(n-i,m-j),mn2=min(n-i,j+1);
            for(int k=1;k<=mn1;k++) ans+=(a[i][j]==a[i+k][j+k]);
            for(int k=1;k<=mn2;k++) ans+=(a[i][j]==a[i+k][j-k]);
        }
    }
    cout<<(ans<<1);
}