首页 > 代码库 > 2017.5 校内预选赛 A H

2017.5 校内预选赛 A H

题目描述:

目前图像识别是一项非常热门的技术,最流行的莫不过是深度学习的图像识别,识别率甚至能达到99%以上。当然,对于简单的图像来说,深度学习是没有必要的。比如如果要识别安徽拼音的首字母A和H,就可以不用深度学习就可以判断。现在有一些只含A或者H的图像,你知道该如何识别吗?

 

输入描述:

       第一行输入正整数T,表示数据的组数。

       每组数据中,第一行是两个正整数n和m,表示图像的大小。

       接下来有n行,每行m个字符,只可能为‘.‘或者‘#‘。‘.‘表示白色,‘#‘表示黑色。‘#‘会通过上下左右或者左上左下右上右下连成一个区域,该区域表示字母。

       数据保证字母在图像内,不会有缺失。

       数据保证图像内只含有A或者H,且除字母外无其他黑色区域。不存在空白图像或者含有其他内容的数据。

       注意,字母不一定是正着的,有可能是斜着横着或者倒着的。

       特别提示:图像一定是白底黑字的,不会存在反色的情况。

 

输出描述

       对于每行数据,输出‘Case t: x‘,x表示你所识别出来的字母。

 

输入样例:

2

3 6

######

..#.#.

...#..

9 21

.....................

...###.......###.....

.....#.........#.....

.....#.........#.....

.....###########.....

.....#.........#.....

.....#.........#.....

...###.......###.....

.....................

 

输出样例:

Case 1: A

Case 2: H

…..#.#

….###

…#.#.

 

 

其实这个题目是我们参加安徽省程序设计大赛时候的一个题目,ljm学长又把这个题目放到校内预选赛中,算是其中的一个较为简单的题目(ps: 团队赛感觉比个人赛有趣)

 

我看见这个题目的思路还是想找A H 这连个字母有是不同,刚开始想到的还是A和H的两个边是不同的,H的两个边平行,A则相交,但是题目A 和 H 但有些样例是不规则的形状,这样仔细想下去,会变得很复杂,所以得转换下思路。那该怎么办呢?

其实可以注意到,A中有个用#围起来的封闭区域,而H没有,那怎么找到这个区域,图的遍历,我用的是dfs。代码如下:

 

#include<iostream>
#include<memory.h>
using namespace std;

int dir1[4]={0,1,0,-1};
int dir2[4]={1,0,-1,0};
int f[100][100]; //表示是否遍历过
char filed[100][100];

void dfs(int x,int y,int n,int m, int &flag){ //引用类型很重要 
    f[x][y]=1;
    for(int i=0;i<4;i++){ //从四个方向递归 
        int dx=x+dir1[i];
        int dy=y+dir2[i];
        if(dx<0 || dx>=n || dy<0 || dy>=m) //判断是否越界 
            flag=1;
        else
            if(filed[dx][dy]==. && f[dx][dy]==0)
                dfs(dx,dy,n,m,flag);
    }
} 

bool solve(int n,int m){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(filed[i][j]==. && f[i][j]==0){            
            //选 filed[i][j]==. 并且没有访问过的点进行搜索 我这里用的是dfs 其实也可以用bfs 
                int flag=0;
                dfs(i,j,n,m,flag);
                if(flag==0)
                    return true;
            }
        }
    }
    return  false;
}
int main(){
    int t;
    cin>>t;
    for(int k=1;k<=t;k++){
        memset(f,0,100*100); //每个样例都重置一下f 
        int n,m;    //图的大小 
        cin>>n>>m;
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>filed[i][j];
            } 
                
        }
        if(solve(n,m))
            cout<<"Case "<<k<<": "<<"A"<<endl;
        else
            cout<<"Case "<<k<<": "<<"H"<<endl;
        
    }    
} 

 

解释下:solve函数里面两个循环,对图中的所有点进行以此if判断,然后对值为‘.‘且没有访问过的点开始遍历,下图为栗子

技术分享

 

从换红线的那个点开始遍历。那就进入dfs函数。看下面一段代码:

for(int i=0;i<4;i++){ //从四个方向递归 
        int dx=x+dir1[i];
        int dy=y+dir2[i];
        if(dx<0 || dx>=n || dy<0 || dy>=m) //判断是否越界 
            flag=1;
        else
            if(filed[dx][dy]==. && f[dx][dy]==0)
                dfs(dx,dy,n,m,flag);
    }

i从0到3代表四个方向,得到下一步应该到的坐标dx dy 然后对dx dy 进行判断,如歌超出0-n 0-m范围,说明x,y 处于边界,如上图所代表的点,那就说明它所在区域不可能四周都被#围住,这个点就是个出口。那么就把它的flag置为1。

A中有一个区域被#围起来,所以flag不会被置为1,还是0,所以在solve中对flag进行判断,如果flag==0 为true 说明为A 直接返回true到主函数。问题得解

 

ps: 注意dfs中的参数是对flag的引用,大家可以把引用去掉看看有什么结果。(有助于理解递归哦)

 

 

看了这篇题解不能理解的同学,可以花一个图按照程序手动推演下这个程序。(可以后台留言,尽量回复)

 

2017.5 校内预选赛 A H