Submission #235647

#	Time	Username	Problem	Language	Result	Execution time	Memory
235647		sbna154	흑백 이미지 찾기 (kriii3_G)	C++14	0 / 101	163 ms	9532 KiB

G

#include <cstdio>
#include <iostream>
#include <math.h>
#include <time.h>

int CompareDoubleAbsoulte(double x, double y, double absTolerance = (1.0e-8))	//실수비교를 위한 함수 
{
    double diff = x - y;				
    if (fabs(diff) <= absTolerance)	//두실수의 차의 절댓값이 엡실론보다작으면 두 실수는 일치한다. 
        return 0;

    return (diff > 0) ? 1 : -1;		//위의경우를 제외한 경우에 대해 x>y면 1을, 아니면 -1을 리턴한다. 
}

bool isMatch(double p, double q, int**A, int**B, int x, int y, int r, int c)	//매칭검사함수 
{
		int a1=A[x][y];			//a1=해당하는 x,y범위에서 A의 값 
		int b1=B[0][0];			//b1=B의 첫번째 숫자 
											//해당 x,y의 범위의 해(p,q)를 구하기 위한 반복문 
			for(int i=0;i<r;i++)			//0~r-1인 i에 대해 
			{			
				for(int j=0;j<c;j++)		//0~c-1인 j에 대해 
				{
					if(a1!=A[x+i][y+j])		//A의 행렬에서 다른숫자 2개를 택해 연립방정식2개 만든다. 
					{						
						int	M[2][2];		//역행렬을 이용하여 방정식의 해인 p,q를 구한다. 
											//p의 계수를 a, c 그리고 q의 계수를 b,d 그리고 각각 매칭되는 B의 값을 k1,k2라 했을때			
						M[0][0] = a1;    	//방정식의해[p,q] = 1/(ad-bc)*[d,-b,-c,a][k1,k2] 이다. 
  						M[0][1] = 1;    	
   						M[1][0] = A[x+i][y+j];   
   						M[1][1] = 1;    
   						p=((double)M[1][1]/(M[0][0]*M[1][1]-M[0][1]*M[1][0]))*B[0][0]+((double)(-1)*M[0][1]/(M[0][0]*M[1][1]-M[0][1]*M[1][0]))*B[i][j];
   						q=((double)(-1)*M[1][0]/(M[0][0]*M[1][1]-M[0][1]*M[1][0]))*B[0][0]+((double)M[0][0]/(M[0][0]*M[1][1]-M[0][1]*M[1][0]))*B[i][j];
   						goto skip;			//해를 구했으므로 더 계산할 필요가 없으므로 반복문을 skip한다. 
   					}
   				}
   			}
	skip:							//매칭여부검사를 위한 반복문 
	for(int i=0;i<r;i++)			//0~r-1인 i에 대해 
	{			
		for(int j=0;j<c;j++)		//0~c-1인 j에 대해 
	 	{							//해를 대입했을때 모든 i,j에 대해 방정식이 성립하면 해당범위의A와 B는 매칭된다. 
			if (CompareDoubleAbsoulte(p*A[x + i][y + j]+ q - B[i][j],0.0)== 0)	//해를 대입했을때 방정식이 성립하면 나머지i,j에 대해서도 검사한다. 
			{
				continue;
			}
			else 				//한경우라도 방정식이 성립하지 않으면 매칭이 아니고 더 계산할 필요가 없으므로 false를 리턴한다. 
				return false;
		}			
	}
	return true;			//위의 반복문을 통과한경우 해를 대입했을때 모든 i,j에 대해 방정식이 성립하였으므로 true를 리턴한다. 
}
int main()
{
	clock_t start = clock();
	
	int n, m;				//nXm인 A행렬 생성 
	std::cin >> n >> m;		
	int **A;
	
	A= new int*[n];			//2차원 포인터선언 
	for(int i=0;i<n;i++)
		A[i]=new int[m];	//각각 크기할당 
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		{
			scanf("%d",&A[i][j]);	//입력받아 채워넣기 
		}
		

	
	int r, c;				//rXc인 B행렬 생성 
	std::cin >> r >> c;		
	int **B;
	
	B= new int*[r];			//2차원 포인터선언 
	for(int i=0;i<r;i++)
		B[i]=new int[c];	//각각 크기할당 
	for(int i=0;i<r;i++)
		for(int j=0;j<c;j++)
		{
			scanf("%d",&B[i][j]);	//입력받아 채워넣기 
		}
	
	double  p,q;	//해 


	int count=0;	//매칭횟수 
	for(int x=0;x<n-r+1;x++)		//0~n-r인 x에 대해 
	{
		for(int y=0;y<m-c+1;y++)	//0~n-r인 y에 대해 검사를 실시한다. 
		{
		
			if(isMatch(p,q,A,B,x,y,r,c))	//해당하는 i,j를 모두 만족하면 매치된다. 
			{
				count++;
			}		
		}
	}
	
	printf("%d\n",count);	//매칭횟수 출력 
	
	
	for (int i = 0; i < n; i++)		//계산이 끝났으므로 이중포인터 메모리할당 제거 
	{
        delete[] A[i];				//1차원포인터의 메모리할당 제거 
    }
    for (int i = 0; i < r; i++) 
	{
        delete[] B[i];				//1차원포인터의 메모리할당 제거 
    }
    delete[] A;						//2차원포인터의 메모리할당 제거 
    delete[] B;						//2차원포인터의 메모리할당 제거 
    
    clock_t end = clock();
    printf("Time : %lf\n", (double)(end - start)/CLOCKS_PER_SEC);	
	
	return 0; 
}

Compilation message (stderr)

G.cpp: In function 'bool isMatch(double, double, int**, int**, int, int, int, int)':
G.cpp:18:7: warning: unused variable 'b1' [-Wunused-variable]
   int b1=B[0][0];   //b1=B의 첫번째 숫자 
       ^~
G.cpp: In function 'int main()':
G.cpp:67:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&A[i][j]); //입력받아 채워넣기 
    ~~~~~^~~~~~~~~~~~~~~
G.cpp:82:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&B[i][j]); //입력받아 채워넣기 
    ~~~~~^~~~~~~~~~~~~~~
G.cpp:94:14: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(isMatch(p,q,A,B,x,y,r,c)) //해당하는 i,j를 모두 만족하면 매치된다. 
       ~~~~~~~^~~~~~~~~~~~~~~~~
G.cpp:94:14: warning: 'q' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 0 / 33
• Subtask 2: 0 / 68