Click here to Skip to main content
15,867,594 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
I need to make a pattern detection code,
with the following conditions:
Given an image (square matrix) A[N,N], if point P(X,Y) is the center of a star, the following condition will be satisfied:

(1) A[X][j]=255, for all 0<=j<N  (The values in the Xth row are all 255)

(2) A[i][Y]=255, for all 0<=i<N  (The values in the Yth column are all 255)

(3) 

    A[X+i][Y+i]=255, for all -N<=i<N if 0<=(X+i)<N and 0<=(Y+i)<N

    A[X+i][Y-i]=255, for all -N<=i<N if 0<=(X+i)<N and 0<=(Y-i)<N

    (The values of two diagonals from the centers are all 255)


I would like to know a way to effectively solve this problem quickly.

What I have tried:

The way that my program works is as follows:
1. receive the input matrix
2. create an empty copy 2d matrix
2. scan for full row values whilst scanning. -> add the value of a the detected row into the copy
3. scan for full column values-> add the value of a the detected col into the copy
4. scan for full diagonal values -> same as above
5. scan for full anti-diagonal values. -> same as above
6. iterate through the copy matrix, and the center of star will be found with a point which has been intersected 4 times.

My full code as follows:

#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;
            }
            //printf("j=%d\n", j);
            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;
            }
            //printf("i=%d\n", size-i);
            //printf("total diagonal=%d\n", totaldiagonal);
            if(totaldiagonal== size-i-1){
                i=size-1;
                j=k;
                //printf("masuk\n");
                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){
                //printf("inside\n");
                int i=size-1;
                int y=j;
                while(y>=0)
                {
                    //printf("coordinates: x=%d, y=%d\n", i,y);
                    //printf("data: %d", constellation[i][y]);
                    copy[i][y]+=1;
                    i--;
                    y-=1;
                }
            }
            totaldiagonal=0;
            //printf("repeat\n");
        }
        
        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++){
                printf("%d ", constellation[i][j]);
            }
            printf("\n");
        }
        printf("\n");
        */
        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++;
				//i have checked whether the edges could be or not be a center of star, but still no difference
                //printf("%d ", copy[i][j]);
            }
            //printf("\n");
        }
        printf("%d\n", counter);
    }
    return 0;
}
Posted
Updated 23-Oct-21 12:54pm
v4
Comments
Patrice T 23-Oct-21 15:47pm    
And you plan to show your code and ask a specific question ?
Bobby Setiawan 23-Oct-21 16:30pm    
I have added the code in the post.
Patrice T 23-Oct-21 16:32pm    
And you have a problem with this code ?
Bobby Setiawan 23-Oct-21 16:35pm    
My Online Judge won't accept the answer given from my code, some of them are wrong answers, and some of them are time limit error. I already made a lot of testcases myself and I don't see wrong with it.
Patrice T 23-Oct-21 16:42pm    
Use Improve question to update your question.
So that everyone can pay attention to this information.

1 solution

Quote:
My Online Judge won't accept the answer given from my code, some of them are wrong answers, and some of them are time limit error. I already made a lot of testcases myself and I don't see wrong with it.

Just from from this quote:
- What happens if there is 1 correct star and other horizontal or vertical lines that are not stars.
- 'Time limit' means that your code is too much brute force. You need to find other ways to get the results with less work.
Example: you know the a line can be part of a star if all points are 255. This also imply that a line is not part of a star at first point that is not 255.
With a matrix of size 1000, your code check 1000000 points, but a clever coding can do the job with checking 2000 points.
C++
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;
}

Take a sheet of paper and a pencil, draw a square matrix of 10*10 and draw a star. Do you need to check all 100 points to detect where is the horizontal lines. you method is your clever algorithm.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900