2015
04-13

# Find the Difference

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 89    Accepted Submission(s): 30

Problem Description
Big Yuer was boring at home during his winter vacation, so he started to play “Find the Difference with beautiful girls” in QQgame.

However, experts are all over the Internet! Big Yuer was beaten again and again.

The evil inside his body began to grow, he decided to make a cheater (matlab version), and he suddenly had a far sight.

This is the working cheater, and the highlighted ones are the differences.

However, he encountered some problems, which need your help.
Suppose two pictures are N*M integer matrix, we define “Trouble Rectangle” between this two as these rectangles: First, the different pixel between them must be in some “Trouble Rectangle”; second, there might be some same pixels inside a “Trouble Rectangle”, but the pixels of the outer boundary must be same in two pictures (the outer boundary means the frame “Trouble Rectangle” produces when expanding 1 pixel larger, except those out side the picture); next, a “Trouble Rectangle” cannot be included in any other “Trouble Rectangle” and cannot be intersect or adjacent to any other “Trouble Rectangle”; at last, each “Trouble Rectangle” must be unable to break down into smaller “Trouble Rectangles”.

Take two 4*4 pictures as example:

In this picture, there are two “Trouble Rectangles”, shown in below.

We cannot take (2,2)-(2,2) as a “Trouble Rectangle” because its outer boundary in two pictures is not same, also we cannot take (1,1)-(2,4) as “Trouble Rectangle” because it can break down into (1,1)-(2,2) and (1,4)-(2,4).
Take a 5*5 one as another example.

There is only one “Trouble Rectangle”, shown in the red line below.

Because (3,3)-(3,3) is included in (1,1)-(5,5), so it’s not a “Trouble Rectangle”.

Input
Multiple test cases (no more than 10), for each case:
The first line contains two integers n and m（n,m <=50）, representing height and length respectively.
Then input two n*m matrix, each number in the matrix is between 0 and 255 inclusive.

Output
For each case:
The first line has one integer X, represent the number of “Trouble Rectangle”.
Following X line, each line output for integers xi1, yi1, xi2 and yi2, representing the coordinate of the top-left and bottom-right points. Output the one with smallest xi1 first, if there’s a tie, output the smallest yi1 first.

Sample Input
4 4
0 0 1 1
0 1 0 0
1 1 1 1
0 0 0 0
1 0 1 0
0 0 0 1
1 1 1 1
0 0 0 0
5 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 0 1 0 1
0 1 1 1 1
1 1 0 1 1
1 1 1 1 1
1 1 1 0 0

Sample Output
2
1 1 2 2
1 4 2 4
2
1 1 3 4
5 4 5 5

Author
zhanyu

Source

Recommend
lcy

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

typedef struct
{
int x1,y1,x2,y2;
}ans;

ans p[10000];
int map1[100][100];
int map2[100][100];
bool s[100][100];
bool vis[100][100];
int up;
int n,m;
int minx,miny,maxx,maxy;

bool Check(ans a,ans b)
{
//   printf("%d...%d...%d...%d\n",max(a.y2,b.y2),min(a.y1,b.y1));
if (max(a.x2,b.x2)-min(a.x1,b.x1)<=a.x2-a.x1+b.x2-b.x1 && max(a.y2,b.y2)-min(a.y1,b.y1)<=a.y2-a.y1+b.y2-b.y1) return true;
return false;
}

void DFS(int x,int y)
{
int i,j;
if (vis[x][y]==1) return;
vis[x][y]=1;
if (minx==x && miny==y && s[x-1][y-1]==1)
{
minx--;
miny--;
DFS(x-1,y-1);
}
if (minx==x && maxy==y && s[x-1][y+1]==1)
{
minx--;
maxy++;
DFS(x-1,y+1);
}
if (maxx==x && miny==y && s[x+1][y-1]==1)
{
maxx++;
miny--;
DFS(x+1,y-1);
}
if (maxx==x && maxy==y && s[x+1][y+1]==1)
{
maxx++;
maxy++;
DFS(x+1,y+1);
}
if (minx==x && s[x-1][y]==1)
{
minx--;
DFS(x-1,y);
}
if (miny==y && s[x][y-1]==1)
{
miny--;
DFS(x,y-1);
}
if (maxy==y && s[x][y+1]==1)
{
maxy++;
DFS(x,y+1);
}
if (maxx==x && s[x+1][y]==1)
{
maxx++;
DFS(x+1,y);
}
if (minx<x) DFS(x-1,y);
if (miny<y) DFS(x,y-1);
if (maxx>x) DFS(x+1,y);
if (maxy>y) DFS(x,y+1);
}

bool cmp(ans a,ans b)
{
if (a.x1!=b.x1) return a.x1<b.x1;
return a.y1<b.y1;
}

int main()
{
int i,j;
ans tag;
bool ok;
while(scanf("%d%d",&n,&m)!=EOF)
{
for (i=0;i<n;i++)
{
for (j=0;j<m;j++)
{
scanf("%d",&map1[i][j]);
}
}
for (i=0;i<n;i++)
{
for (j=0;j<m;j++)
{
scanf("%d",&map2[i][j]);
}
}
memset(s,0,sizeof(s));
for (i=0;i<n;i++)
{
for (j=0;j<m;j++)
{
s[i+1][j+1]=(map1[i][j]!=map2[i][j]);
}
}
up=0;
memset(vis,0,sizeof(vis));
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
{
if (s[i][j]==1 && vis[i][j]==0)
{
maxx=minx=i;
maxy=miny=j;
DFS(i,j);
p[up].x1=minx;
p[up].y1=miny;
p[up].x2=maxx;
p[up].y2=maxy;
up++;
//   debug();
}
}
}
while(1)
{
ok=0;
for (i=0;i<up;i++)
{
for (j=i+1;j<up;j++)
{
if (Check(p[i],p[j])==true)
{
ok=1;
tag.x1=min(p[i].x1,p[j].x1);
tag.y1=min(p[i].y1,p[j].y1);
tag.x2=max(p[i].x2,p[j].x2);
tag.y2=max(p[i].y2,p[j].y2);
p[i]=tag;
p[j]=p[up-1];
up--;
}
}
}
if (ok==0) break;
}
sort(p,p+up,cmp);
printf("%d\n",up);
for (i=0;i<up;i++)
{
printf("%d %d %d %d\n",p[i].x1,p[i].y1,p[i].x2,p[i].y2);
}
}
return 0;
}


, ,
1. 我没看懂题目
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
第二个是7 0 6 -1 1 -6 7输出是14 7 7
不知道题目例子是怎么得出来的

2. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。

3. 第23行：
hash = -1是否应该改成hash[s ] = -1

因为是要把从字符串s的start位到当前位在hash中重置

修改提交后能accept，但是不修改居然也能accept

4. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish