首页 > 搜索 > DFS搜索 > hdu 2472 Image Processing-DFS-[解题报告]C++
2014
01-26

hdu 2472 Image Processing-DFS-[解题报告]C++

Image Processing

问题描述 :

According to Wikipedia, image processing is any form of signal processing for
which the input is an image, such as photographs or frames of video; the output of image processing can be either an image or a set of characteristics or parameters related to the image. Most image-processing techniques involve treating the image as a two-dimensional signal and applying standard signal-processing techniques to it.
The task you are facing here is a relatively easy one (compared to our general
conception of image processing!). Given a black-and-white image of size R * C with some digits (and possibly other shapes) on it, your program needs to figure out the digits written on the image. Specifically, the digits drawn on the graph will adhere to the following rules:
1) Digits are drawn with a series of strokes. A stroke can be regarded as a
rectangle of any size on the image, and its edges will always be parallel to
either x-axis or y-axis. The number of strokes required to draw each digit will
be exactly as follows:

Refer to Figure 2 if you’re unclear about how the digits are drawn.
2) Although the width of strokes used to draw a digit might be different, the outer shapes of digits will strictly follow those specified in Figure 2.
3) In order for a digit to be recognizable, all parts (strokes and joints) presented in the graph below must also be clearly distinguishable in the image.
(Refer to the last sample test case if you are unsure about this requirement;
in that test case, when the middle stroke of 2 is omitted, the number should
not be considered as recognizable.)
4) You may assume that the image is not rotated, and there is no noise in the input.

Please output the sum of digits recognizable in the graph. In the case that no
characters is recognizable, please output 0 instead.

输入:

There are multiple test cases in the input file.
Each test case starts with two integers, R and C ( 1 ≤ R,C ≤ 500), specifying the number of rows / columns of the graph. Each of the following R lines contains consecutive C characters (‘0’ or ‘1’), describing the image to be processed.
Two successive test cases are separated by a blank line. A case with R = 0, C = 0 indicates the end of the input file, and should not be processed by your program.

输出:

There are multiple test cases in the input file.
Each test case starts with two integers, R and C ( 1 ≤ R,C ≤ 500), specifying the number of rows / columns of the graph. Each of the following R lines contains consecutive C characters (‘0’ or ‘1’), describing the image to be processed.
Two successive test cases are separated by a blank line. A case with R = 0, C = 0 indicates the end of the input file, and should not be processed by your program.

样例输入:

5 12
001101011111
000101000011
000101001111
001101000011
000000000111
5 3
111
010
110
010
110
6 14
11111000011111
11001000000011
11111001000000
11111001001110
11001011001010
11111000001110
5 2
11
01
11
01
11
6 9
111100111
000100001
000100011
011100010
010000011
011110000
0 0

样例输出:

Case #1: 4
Case #2: 0
Case #3: 15
Case #4: 3
Case #5: 2

hoj 2472 IR-Lab 
/*

题目:

 

       值班问题,给出所有人的空余时间,问能不能够在每一个时间里安排一个人值班

 

分析:

       二分匹配问题,按人与他的空余时间连线构图,然后就是hungry算法了,简单

*/

 

#include <iostream>

 

#include <cstring>

 

#include <cstdio>

 

using namespace std;

 

#define X 22

 

bool g[X][X],use[X];

 

int xm[X],ym[X],k,p;

 

bool dfs(int u)

 

{

 

       for(int v=0;v<k;v++)

 

              if(g[u][v]&&!use[v])

 

              {

 

                     use[v] = true;

 

                     if(ym[v]==-1||dfs(ym[v]))

 

                     {

 

                            xm[u] = v;

 

                            ym[v] = u;

 

                            return true;

 

                     }

 

              }

 

              return false;

 

}

 

int hungry()

 

{

 

       int ret = 0;

 

       memset(xm,-1,sizeof(xm));

 

       memset(ym,-1,sizeof(ym));

 

       for(int u=0;u<p;u++)

 

              if(xm[u]==-1)

 

              {

 

                     memset(use,false,sizeof(use));

 

                     if(dfs(u))

 

                            ret++;

 

              }

 

              return ret;

 

}

 

int main()

 

{

 

       freopen("sum.in","r",stdin);

 

       freopen("sum.out","w",stdout);

 

       while(cin>>k>>p,k||p)

 

       {

 

              int t,x;

 

              memset(g,false,sizeof(g));

 

              for(int i=0;i<p;i++)

 

              {

 

                     scanf("%d",&t);

 

                     while(t–)

 

                     {

 

                            scanf("%d",&x);

 

                            g[i][x] = true;//该人与他的空余时间连通

 

                     }

 

              }

 

              if(hungry()==k)                 //如果能够安排好的话

 

                     printf("yes\n");

 

              else

 

                     printf("no\n");

 

              //printf("%d\n",hungry());

 

       }

 

       return 0;

 

}

 

 

解题转自:http://hi.baidu.com/15986563445/item/4019204fd86618f1a5c066bc


  1. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.