| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 235647 | 2020-05-29T05:48:55 Z | sbna154 | 흑백 이미지 찾기 (kriii3_G) | C++14 | 163 ms | 9532 KB |
#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
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 6 ms | 384 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 163 ms | 9532 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |