首页 > 搜索 > DFS搜索 > hdu 4414-finding crosses-dfs-[解题报告]hoj
2015
07-16

hdu 4414-finding crosses-dfs-[解题报告]hoj

Finding crosses

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

Problem Description
The Nazca Lines are a series of ancient geoglyphs located in the Nazca Desert in southern Peru. They were designated as a UNESCO World Heritage Site in 1994. The high, arid plateau stretches more than 80 kilometres (50 mi) between
the towns of Nazca and Palpa on the Pampas de Jumana about 400 km south of Lima. Although some local geoglyphs resemble Paracas motifs, scholars believe the Nazca Lines were created by the Nazca culture between 400 and 650 AD.[1] The hundreds of individual
figures range in complexity from simple lines to stylized hummingbirds, spiders, monkeys, fish, sharks, orcas, llamas, and lizards.

Above is the description of Nazca Lines from Wikipedia. Recently scientists found out that those lines form many crosses. Do those crosses have something to do with the Christian religion? Scientists are curious about this. But at first, they want to figure
out how many crosses are there. So they took a huge picture of Nazca area from the satellite, and they need you to write a program to count the crosses in the picture.

To simplify the problem, we assume that the picture is an N*N matrix made up of ‘o’ and ‘#’, and some ‘#’ can form a cross. Here we call three or more consecutive ‘#’ (horizontal or vertical) as a "segment".

The definition of a cross of width M is like this:

1) It’s made up of a horizontal segment of length M and a vertical segment of length M.
2) The horizontal segment and the vertical segment overlap at their centers.
3) A cross must not have any adjacent ‘#’.
4) A cross’s width is definitely odd and at least 3, so the above mentioned "centers" can’t be ambiguous.
For example, there is a cross of width 3 in figure 1 and there are no cross in figure 2 ,3 and 4.

You may think you find a cross in the top 3 lines in figure 2.But it’s not true because the cross you find has a adjacent ‘#’ in the 4th line, so it can’t be called a "cross". There is no cross in figure 3 and figure 4 because of the same reason.

 

Input
There are several test cases.
In each test case:
The First line is a integer N, meaning that the picture is a N * N matrix ( 3<=N<=50) .

Next N line is the matrix.
The input end with N = 0
 

Output
For each test case, output the number of crosses you find in a line.
 

Sample Input
4 oo#o o### oo#o ooo# 4 oo#o o### oo#o oo#o 5 oo#oo oo#oo ##### oo#oo oo##o 6 ooo#oo ooo##o o##### ooo#oo ooo#oo oooooo 0
 

Sample Output
1 0 0 0
 

Source
 
题意:找图中十字架的个数,十字架必须独立,对称才算,不能与其他’#‘相连。
我的思路就是找到十字架的中心,从中心往四周搜,代码能力还是很差,写的冗长:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

char mp[60][60];
int dir[4][2]={-1,0,0,1,1,0,0,-1};
int n,up,down,le,ri;
bool flag;

bool Isok(int x,int y)
{
    if (x>0&&x<=n&&y>0&&y<=n&&mp[x][y]=='#')
        return true;
    return false;
}

void dfs_up(int x,int y)
{
    int dx=x+dir[0][0];
    int dy=y+dir[0][1];
    if (Isok(dx,dy))
    {
        if (mp[dx][dy-1]=='#'||mp[dx][dy+1]=='#')
        {
            flag=false;
            return ;
        }
        mp[dx][dy]='.';
        up++;
        dfs_up(dx,dy);
    }
    return ;
}

void dfs_down(int x,int y)
{
    int dx=x+dir[2][0];
    int dy=y+dir[2][1];
    if (Isok(dx,dy))
    {
        if (mp[dx][dy-1]=='#'||mp[dx][dy+1]=='#')
        {
            flag=false;
            return ;
        }
        mp[dx][dy]='.';
        down++;
        dfs_down(dx,dy);
    }
    return ;
}

void dfs_le(int x,int y)
{
    int dx=x+dir[3][0];
    int dy=y+dir[3][1];
    if (Isok(dx,dy))
    {
        if (mp[dx-1][dy]=='#'||mp[dx+1][dy]=='#')
        {
            flag=false;
            return ;
        }
        mp[dx][dy]='.';
        le++;
        dfs_le(dx,dy);
    }
    return ;
}

void dfs_ri(int x,int y)
{
    int dx=x+dir[1][0];
    int dy=y+dir[1][1];
    if (Isok(dx,dy))
    {
        if (mp[dx+1][dy]=='#'||mp[dx-1][dy]=='#')
        {
            flag=false;
            return ;
        }
        mp[dx][dy]='.';
        ri++;
        dfs_ri(dx,dy);
    }
    return ;
}

int main()
{
    while (scanf("%d",&n)&&n)
    {
        memset(mp,'o',sizeof(mp));
        getchar();
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
                scanf("%c",&mp[i][j]);
            getchar();
        }
        int ans=0;
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
            {
                if (mp[i][j]=='#')
                {
                    int f=1;
                    for (int t=0;t<4;t++)
                        if (mp[ i+dir[t][0] ][ j+dir[t][1] ]!='#')
                        {
                            f=0;
                            break;
                        }
                    if (f)
                    {
                        flag=true;
                        up=0,down=0,le=0,ri=0;
                        dfs_up(i,j);
                        dfs_down(i,j);
                        dfs_le(i,j);
                        dfs_ri(i,j);
                        if (flag)
                        {
                            if (up==down&&down==le&&le==ri&&up!=0)
                                ans++;
                        }
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。


, ,
  1. 黑自己祖国会有神马幽默感?抱怨能解决神马?你可以不爱这个国家但是你不能在享受了这个国家带给你的利益后,还能心安理得的说这个。。。这样对的起你的良心?

  2. 黑自己祖国会有神马幽默感?抱怨能解决神马?你可以不爱这个国家但是你不能在享受了这个国家带给你的利益后,还能心安理得的说这个。。。这样对的起你的良心?

  3. 黑自己祖国会有神马幽默感?抱怨能解决神马?你可以不爱这个国家但是你不能在享受了这个国家带给你的利益后,还能心安理得的说这个。。。这样对的起你的良心?

  4. 黑自己祖国会有神马幽默感?抱怨能解决神马?你可以不爱这个国家但是你不能在享受了这个国家带给你的利益后,还能心安理得的说这个。。。这样对的起你的良心?

  5. 黑自己祖国会有神马幽默感?抱怨能解决神马?你可以不爱这个国家但是你不能在享受了这个国家带给你的利益后,还能心安理得的说这个。。。这样对的起你的良心?