The Ninth Hunan Collegiate Programming Contest (2013) Problem C

2023-08-14 23:47:16

Problem C

Character Recognition?

Write a program that recognizes characters. Don't worry, because you only need to recognize three digits: 1, 2 and 3. Here they are:

.*.  ***  ***

.*.  ..*  ..*

.*.  ***  ***

.*.  *..  ..*

.*.  ***  ***

Input

The input contains only one test case, consisting of 6 lines. The first line contains n, the number of characters to recognize (1<=n<=10). Each of the next 5 lines contains 4n characters. Each character contains exactly 5 rows and 3 columns of characters followed by an empty column (filled with '.').

Output

The output should contain exactly one line, the recognized digits in one line.

Sample Input

3

.*..***.***.

.*....*...*.

.*..***.***.

.*..*.....*.

.*..***.***.

Output for the Sample Input

The Ninth Hunan Collegiate Programming Contest (2013) Problemsetter: Rujia Liu Special Thanks: Feng Chen, Md. Mahbubul Hasan

方法很多，深入理解dfs即可方便解决此题 ,我觉得这个方法比较好，有一定的价值。

#include <iostream>

#include <stdio.h>

#include <queue>

#include <stdio.h>

#include <string.h>

#include <vector>

#include <queue>

#include <set>

#include <algorithm>

#include <map>

#include <stack>

#include <math.h>

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std ;

typedef long long LL ;

struct Point{

    int  X ;

    int  Y ;

    Point(){} ;

    Point(int x ,int y):X(x),Y(y){} ;

};

char str[][] ;

int N  ;

int d[][]={{,},{-,},{,-},{,}} ;

bool visited[][] ;

vector<Point>my_hash[] ;

int cango(int x ,int y){

    return <=x&&x<=&&<=y&&y<=*N&&str[x][y]=='*';

}

void dfs(int x ,int y ,int color){

     my_hash[color].push_back(Point(x,y)) ;

     visited[x][y]= ;

     for(int i=;i<;i++){

          int xx=x+d[i][] ;

          int yy=y+d[i][]  ;

          if(cango(xx,yy)&&!visited[xx][yy]){

               dfs(xx,yy,color) ;

          }

     }

}

int main(){

    int color= ;

    scanf("%d",&N) ;

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

         scanf("%s",str[i]+) ;

    for(int i=;i<=N;i++)

        my_hash[i].clear() ;

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

       for(int j=;j<=*N;j++){

           if(str[i][j]=='*'&&!visited[i][j]){

               color++ ;

               dfs(i,j,color) ;

           }

    }

    for(int i=;i<=N;i++){

        Point first = my_hash[i][] ;

        Point second = my_hash[i][my_hash[i].size()-] ;

        if(first.Y==second.Y&&first.X+==second.X)

            putchar('') ;

        else if(first.Y<second.Y)

            putchar('') ;

        else if(first.X+==second.X)

            putchar('') ;

    }

    puts("") ;

    return  ;

}