首页 > 搜索 > DFS搜索 > hdu 3885-find the difference-dfs-[解题报告]hoj
2015
04-13

hdu 3885-find the difference-dfs-[解题报告]hoj

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

错了好多次才过,好吧,我的人生价值是用来创造罚时的……呕耶!

这题给两个像素图,然后让你求出这个图中有多少个trouble rectangle,其定义为一个矩形,里面必须有一些像素点值不同,两个矩形不能相邻(周围八个方向),而且不能嵌套。

先dfs下所有的相邻的方块,之后相邻的合并。后来想想不用dfs,只需要找出所有不同的方块,之后用这些方块合并就行了,写长了……

代码,没什么利用价值,不过按照惯例还是贴一下吧

#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