Finding crosses

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

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

Source

2012 ACM/ICPC Asia Regional Hangzhou Online

Recommend

liuyiding

题意：给你一个 n*n 的图（3 <= n <= 50）

找出有多少个十字架，输出结果

十字架结构：由 "#" 构成，十字架周围不可以有 "#" 才满足条件

比如说这个图：有一个十字架，那么红色区域都不能够是 "#", 否则一个十字架也没有，输出 0 .

算法：等于没有算法，dfs 应该可以做，但是简单暴力枚举即可秒过。

ＰＳ：英文很吓人啊，比赛的时候看到一堆英文就吓到了，结果是道水题ORZ

Accepted

4414

0MS

232K

1726 B

C++

free斩

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;

const int maxn = 60;
char map[maxn][maxn];
int n;

bool check(int x, int y)
{
    int lenUp = 0;
    //up
    for(int j = y-1; j >= 0; j--) //向上走确定十字架的形状
    {
        if(map[x][j] != '#') break;
        else if(map[x-1][j] == '#' || map[x+1][j] == '#') return false;
        else lenUp++;
    }
    if(lenUp == 0) return false;

    //down
    int lenDown = 0;
    for(int j = y+1; j < n; j++)
    {
        if(map[x][j] != '#') break;
        else if(map[x-1][j] == '#' || map[x+1][j] == '#') return false;
        else lenDown++;
    }
    if(lenDown != lenUp) return false;

    int lenLeft = 0;
    for(int i = x-1; i >= 0; i--)
    {
        if(map[i][y] != '#') break;
        else if(map[i][y-1] == '#' || map[i][y+1] == '#') return false;
        else lenLeft++;
    }
    if(lenLeft != lenUp) return false;

    int lenRight = 0;
    for(int i = x+1; i < n; i++)
    {
        if(map[i][y] != '#') break;
        else if(map[i][y-1] == '#' || map[i][y+1] == '#') return false;
        else lenRight++;
    }
    if(lenRight != lenUp) return false;

    return true;
}
int main()
{
    while(scanf("%d", &n) != EOF)
    {
        if(n == 0) break;
        memset(map,'o',sizeof(map));

        for(int i = 0; i < n; i++)
        {
             scanf("%s", map[i]);
        }

        int ans = 0;
        for(int i = 1; i < n-1; i++)
        {
            for(int j = 1; j < n-1; j++)
            {
                if(map[i][j] == '#' && check(i,j))
                    ans++;
            }
        }
        printf("%d
", ans);
    }
    return 0;
}