Submission #15516

#	Time	Username	Problem	Language	Result	Execution time	Memory
15516		pichulia	흑백 이미지 찾기 (kriii3_G)	C++98	33 / 101	10000 ms	12888 KiB

G

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int n, m;
int p,q;
int a[1003][1003];
int b[1004][1004];
int c[1004][1004];
int gcd(int p,int q)
{
	if(p<0)p=-p;
	if(q<0)q=-q;
	if(p==0)return q;
	if(q==0)return p;
	while(p%q){int t=p%q;p=q;q=t;}
	return q;
}
int main()
{
	int i, j ,k, l;
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			scanf("%d",&a[i][j]);
	scanf("%d %d",&p,&q);
	for(i=0;i<p;i++)
		for(j=0;j<q;j++)
			scanf("%d",&b[i][j]);
	int g = 0;
	k= b[0][0];
	for(i=0;i<p;i++)
		for(j=0;j<q;j++)
		{
			b[i][j] -= k;
			g = gcd(g,b[i][j]);
		}
	bool special = false;
	if(g>0)
	for(i=0;i<p;i++)
		for(j=0;j<q;j++)
			b[i][j] /= g;
	else
		special = true;
	int cnt=0;
	for(i=0;i<=n-p;i++)
		for(j=0;j<=m-q;j++)
		{
			if(special)
			{
				cnt++;
				continue;
			}
			int t = a[i][j];
			int g = 0;
			for(k=0;k<p;k++)
				for(l=0;l<q;l++)
				{
					c[k][l] = a[i+k][j+l] - t;
					g = gcd(g,c[k][l]);
				}
			if(g>0)
			for(k=0;k<p;k++)
				for(l=0;l<q;l++)
					c[k][l] /= g;

			for(k=0;k<p;k++)
			{
				for(l=0;l<q;l++)
					if(c[k][l]!=b[k][l])
						break;
				if(l<q)break;
			}
			if(k<p)
			{
				for(k=0;k<p;k++)
				{
					for(l=0;l<q;l++)
						if(c[k][l]!=-b[k][l])
							break;
					if(l<q)break;
				}
				if(k==p)
					cnt++;
			}
			else
				cnt++;	
		}
	printf("%d\n",cnt);
}

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