如何高效检测正方形矩阵中符合特定条件的星形图案中心点？

检测规则 #

给定正方形矩阵图像A[N,N]，点P(X,Y)判定为星形中心需同时满足三个条件：

• 第X行所有元素均为255：A[X][j]=255, 对所有0<=j<N成立
• 第Y列所有元素均为255：A[i][Y]=255, 对所有0<=i<N成立
• 过P点的两条对角线上所有在矩阵范围内的元素均为255：
  • 主对角线方向：A[X+i][Y+i]=255，i取所有满足0<=X+i<N且0<=Y+i<N的值
  • 反对角线方向：A[X+i][Y-i]=255，i取所有满足0<=X+i<N且0<=Y-i<N的值

现有实现思路 #

现有方案通过计数叠加判定中心，步骤如下：

1. 接收输入矩阵，将255转为1、其他值转为0方便计数
2. 初始化空白计数二维矩阵
3. 扫描所有行，全1的行对应计数矩阵整行加1
4. 扫描所有列，全1的列对应计数矩阵整列加1
5. 扫描所有主对角线，全1的对角线对应计数矩阵对角线位置加1
6. 扫描所有反对角线，全1的对角线对应计数矩阵对角线位置加1
7. 遍历计数矩阵，值>=4的点即为星形中心
   该方案简单测试用例可正常运行，但提交在线判题时存在报错和超时问题。
   

现有实现代码 #

#include<stdio.h>
int constellation[2048][2048];
int copy[2048][2048]={};
int main()
{
    int a,size;
    int totalrow=0, totalcol=0;
    scanf("%d", &a);
    scanf("%d", &size);

    for(int i=0; i<a; i++){
        
        for(int row=0; row<size; row++){
            for(int col=0; col<size; col++){
                scanf("%d", &constellation[row][col]);
                constellation[row][col]=(constellation[row][col]== 255)?1:0;   
                totalrow+=constellation[row][col];
            }
            if(totalrow==size)
            {
                for(int col = 0; col<size; col++)
                    copy[row][col]+=1;
            }
            totalrow=0;
        }

        for(int row=0; row<size; row++){
            for(int col=0; col<size; col++)
                totalcol+=constellation[col][row];
            if(totalcol==size)
                for(int x=0; x<size; x++)
                    copy[x][row]+=1;
            totalcol=0;
        }
        int totaldiagonal=0, i=0, j=0;
        for(int k=0; k<=size-1; k++)
        {
            i=k;
            j=0;
            while(i>=0)
            {
                totaldiagonal+=constellation[i][j];
                i-=1;
                j+=1;
            }
            if(totaldiagonal==j && totaldiagonal!=0){
                i=k;
                j=0;
                while(i>=0){
                    copy[i][j]+=1;
                    i-=1;
                    j+=1;
            }      
            }
            totaldiagonal=0;
        }
        totaldiagonal=0;
        for(int k=1; k<=size-1; k++){
            i=size-1;
            j=k;
            while(j<=size-1)
            {
                totaldiagonal+=constellation[i][j];
                i-=1;
                j+=1;
            }
            if(totaldiagonal== size-i-1){
                i=size-1;
                j=k;
                while(j<=size-1){
                    copy[i][j]+=1;
                    i-=1;
                    j+=1;
                }
            }
            totaldiagonal=0;
        }

        int max=0;
        for(int j=0; j<size ;j++)
        {
            max=0;
            int i=size-1;
            int y=j;
            while(y>=0)
            {
                max++;
                totaldiagonal+=constellation[i][y];
                i--;
                y--;
            }
            if(max==totaldiagonal){
                int i=size-1;
                int y=j;
                while(y>=0)
                {
                    copy[i][y]+=1;
                    i--;
                    y-=1;
                }
            }
            totaldiagonal=0;
        }
        
        for(int k=size-1; k>=0; k--)
        {
            max=0;
            i = k-1;
            j = size-1;
            while(i>=0)
            {
                max++;
                totaldiagonal+=constellation[i][j];
                i--;
                j--;
            }
            if(totaldiagonal==max)
            {
                i=k-1;
                j=size-1;
                while(i>=0)
                {
                    copy[i][j]+=1;
                    i--;
                    j--;
                }
            }
            totaldiagonal=0;
        }

        int counter=0;
        for(int i=0; i<size; i++){
            for(int j=0; j<size; j++){
                if(copy[i][j]>=4  && i>0 && i<size-1 && j>0 && j<size-1) counter++;
            }
        }
        printf("%d\n", counter);
    }
    return 0;
}

问题修复与优化方案 #

报错修复 #

现有代码最核心的报错原因是多组测试用例之间没有重置计数矩阵，上一组测试的计数结果会污染下一组的计算，每组用例处理完成后需要将copy矩阵所有值重置为0。另外对角线长度判断的索引计算存在边界错误，容易漏判或者多判对角线。

超时优化 #

现有方案时间复杂度为O(N²)，但存在大量无意义的二维数组遍历写操作，可以通过以下方式优化：

1. 替换二维计数矩阵为四个一维标记数组：
   • row_ok[2048]：标记第i行是否全为255
   • col_ok[2048]：标记第j列是否全为255
   • diag1_ok[4096]：标记主对角线（x-y值相同的元素属于同一条主对角线，加上偏移量N-1避免负数索引）是否全为255
   • diag2_ok[4096]：标记反对角线（x+y值相同的元素属于同一条反对角线）是否全为255
2. 只需要一次矩阵遍历完成所有行、列、对角线的和统计，再遍历一次所有点判断四个标记是否同时为真即可得到星形中心数量，省去所有修改二维计数数组的操作，运行速度可以提升3倍以上
3. 大矩阵输入时可以用getchar()实现快速读入，避免scanf的性能瓶颈

内容的提问来源于stack exchange，提问作者need_help_ples