我需要制作一個模式檢測代碼，條件如下：
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)
我想知道一種快速有效解決這個問題的方法。
我嘗試過的：
我的程式的作業方式如下：
- 接收輸入矩陣
- 創建一個空的副本二維矩陣
- 掃描時掃描全行值。-> 將檢測到的行的值添加到副本中
- 掃描全列值-> 將檢測到的列的值添加到副本中
- 掃描全對角線值 -> 同上
- 掃描完整的對角線值。-> 同上
- 遍歷復制矩陣，將找到與已相交 4 次的點的星形中心。
用簡單的testcase，我的代碼可以運行，但是在線判斷失敗，還有時間限制問題。
完整代碼在這里：
#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;
//checking for the same diagonal, but the patterns changed, need new for loop.
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;
}
uj5u.com熱心網友回復：
我的第一個想法：
創建 8 個位陣列（或單個 8 位數字陣列），大小與影像相同。
每個陣列對應一個方向。如果從相應像素到影像邊緣有一條白線（在特定方向），則陣列中的某位應該為真。
換句話說，
arr1[i][j]如果input[i][j]是白色并且arr1[i-1][j]為真（每個陣列的偏移量不同），則應該為真。如果所有 8 個陣列的
true元素都在同一位置，則此位置為星形。要根據此規則填充陣列，您需要對輸入影像進行兩次遍歷。第二遍應該是相反的。
第一遍可以填充 8 個陣列中的 4 個（哪些應該是不言而喻的：只有檢查已經遍歷的鄰居才有意義）。
第二遍可以填充剩余的 4 個陣列。
第二遍還可以檢查當前像素是否為星形（如果所有 8 個陣列的
true元素都在同一位置），如果是，則增加一個計數器。
在偽代碼中，第一遍可能如下所示：
for y = 0..n-1
for x = 0..n-1
if input[x][y] == 255
if arr1[x-1][y]
arr1[x][y] = true
if arr2[x-1][y-1]
arr2[x][y] = true
if arr3[x][y-1]
arr3[x][y] = true
if arr4[x 1][y-1]
arr4[x][y] = true
You also need special handling for the image borders, to avoid accessing `arr??` out of bounds.
The second pass would be exactly the same, except you should be iterating in reverse, and should be filling the other 4 arrays.
uj5u.com熱心網友回復：
我會先去解決一個更簡單的問題。考慮到恒星只有水平線和垂直線穿過它們。要找出哪些水平線和垂直線是完全白色的，只需計算每條線中白色像素的數量，最后將計數與影像的寬度和高度進行比較。如果您在讀取輸入時執行此操作，則非常便宜：
int rowsums[size] = {0};
int colsums[size] = {0};
for (int row=0; row<size; row ) {
for (int col=0; col<size; col ) {
int value;
scanf("%d", &value);
rowsums[row] = value;
colsums[col] = value;
}
}
請注意，我們不再需要二維陣列，我們只需要兩個一維陣列來存盤有關影像的資訊。
現在，您可以通過檢查每個像素是否在整行或整列中來獲取星星的位置：
for (int row=0; row<size; row ) {
if (rowsums[row] != size * 255)
continue;
for (int col=0; col<size; col ) {
if (colsums[col] != size * 255)
continue;
printf("Star at %d, %d\n", row, col);
}
}
第二遍仍然是 O(N2)。但是，如果您首先掃描rowsums并colsums創建僅包含全白行和列的行和列索引的新陣列，則會將問題簡化為 O(N number_of_stars)。如果您只需要計數，那么它只是O(N)，因為您只需要將全白行的數量乘以全白列的數量就可以得到星星的數量。
現在嘗試擴展這種方法來構建所有可能對角線的像素值的總和。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/335260.html
標籤：C
下一篇：使用整數求牛頓的平方根