15,881,248 members
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:
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
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.

## Solution 1

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.