阜博通2013校园招聘 上机题

The videos from varios video sharing web sites may contain the logos of the web sites. We usually need to detect the logos before further processing. Now you are asked to write a program to detect the logo.

To simplify the problem, here we have some assumtions on the logo.

The logo is a rectangle parallel to the axis. The position of the logo does not change among different frames. The color of the logo does not change much among different frames, that is, the color of each pixel in grey scale differs no more thanD.

Given two frames of the video in grey scale, you are asked to determine the largest area that may be a logo.

Input Specification:

Each file contains one test case. The first line of each test case contains 3 integersN,M andD (0 <N,M ≤ 1000, 0 ≤ D ≤ 255). ThenN lines follow, each of each containsM integers between 0 and 255, inclusive, describing the first frame. Then anotherN lines ofM integers between 0 and 255, both inclusive, follow, describing another frame.

Output Specification:

For each test case, output the left-bottom coordinates and the right-top coordinates of the largest logo in one line. If there are multiple logos having the same area, output the one that lexicographically come first. That is to say, first minimize the smaller x coordinate, then minimize the smaller y coordinate and etc. If there is no available logo area, output "-1 -1 -1 -1" (without quotes) instead.

Sample Input 1:

5 5 01 1 1 1 11 1 1 1 11 1 1 1 11 1 1 1 11 1 1 1 10 0 0 0 00 0 1 0 00 0 0 0 00 0 0 0 00 0 0 0 0

Sample Output 1:

3 4 3 4

Sample Input 2:

4 4 10127 143 231 123174 225 240 218230 255 255 234228 234 251 201147 150 230 150180 220 240 220230 255 255 240150 230 250 180

Sample Output 2:

1 2 4 3

存在以下几个问题：1.直接创建1000×1000的int数组是非法的，栈的一搬默认大小为1M，是无法创建的2.坐标轴转化的问题，大家仔细想想就行了3.顺序的问题，即有相同最大面积区域的时候，应该选取哪一块区域。相信很多人挂在这上面，其实只要改变一个遍历时行列顺序即可ps：应该有效率更优的方法，当时只想到这个。。。

#include <iostream>#include <stdio.h>int main(){int i,j;int N,M,D,temp;scanf("%d %d %d",&N,&M,&D);bool **differ=new bool*[N];char **pa=new char*[N];char **pb=new char*[N];for(i=0;i<5;i++){differ[i]=new bool[M];pa[i]=new char[M];pb[i]=new char[M];}//输入数据for(i=0;i<N;i++)for(j=0;j<M;j++)scanf("%d",&pa[i][j]);for(i=0;i<N;i++)for(j=0;j<M;j++)scanf("%d",&pb[i][j]);//判断每个点是否符合条件for(i=0;i<N;i++)for(j=0;j<M;j++){temp=pa[i][j]-pb[i][j];if(temp<=D&&temp>=-D)differ[i][j]=true;elsediffer[i][j]=false;}//寻找最大的logo区域int firstx=-1,firsty=-1,endx=-1,endy=-1,max;for(j=0;j<M;j++)for(i=N-1;i>=0;i--)if(differ[i][j]){for(int k=0;k<=i;k++)for(int l=M-1;l>=j;l--)if(differ[k][l]&&(i-k+1)*(l-j+1)>max){int t=k,s=l;bool test=differ[t][s];while(test&&t<=i){s--;if(s<j){t++;s=l;}if(t<=i)test=test&differ[t][s];}if(test){max=(i-k+1)*(l-j+1);firstx=j+1;firsty=N-i;endx=l+1;endy=N-k;}}}printf("%d %d %d %d",firstx,firsty,endx,endy);delete[] differ;delete[] pa;delete[] pb;return 0;}