UCI2009D - Digger Octaves
After many years spent playing Digger, little Ivan realized he was not taking advantage of the octaves. Oops, sorry! Most of you were not born when Digger came to light!
Digger is a Canadian computer game, originally designed for the IBM personal computer, back in 1983. The aim of the game is to collect precious gold and emeralds buried deep in subterranean levels of and old abandoned mine.
We Digger gurus call a set of eight consecutive emeralds an octave. Notice that, by consecutive we mean that we can collect them one after another. Your Digger Mobile is able to move in the four directions: North, South, West and East.
In a simplified Digger version, consisting only of emeralds and empty spaces, you will have to count how many octaves are present for a given map.
Input
Input starts with an integer T, representing the number of test cases (1<=T<=20). Each test case consists of a map, described as follows:
An integer N (1<=N<=8), representing the side length of the square-shaped map. N lines follow, N characters each. A 'X' character represents an emerald, and a '.' represents an empty space.
Output
For each test case print the number of octaves on a single line.
Example
Input:
2
3
XXX
X.X
XXX
3
XXX
XXX
XXX
Output: 1
5
hide comments
xamitksx:
2016-03-24 07:04:01
bookeeping of already found Octave is must for uniqueness
|
|
mkmostafa:
2015-09-08 02:08:26
when a . is encountered, do we stop the search in that path? i.e is XXXX.XXXX considered an octave?? |
|
Rishav Goyal:
2014-06-03 23:19:12
nice problem :) Last edit: 2014-06-03 23:19:22 |
|
Gitu:
2013-07-25 14:17:53
@ Intelligent Idiot
|
|
Intelligent Idiot:
2013-07-25 11:10:03
@Gitanshu
|
|
Gitu:
2013-07-25 05:57:50
I think my algorithm is working fine, but getting WA... Is there any tricky test case?
|
|
Paul Draper:
2012-11-20 02:18:38
[Trichromatic] XilinX is correct in that traversing the octave one way or another does not matter, but note what :D said: there still must be an ordered way to traverse the octave in a contiguous manner. |
|
:D:
2011-06-03 07:40:38
You must skip one emerald. It can be one in the middle or 4 in the vertices. 4 in the middle of the edges can't be chosen, because you can't make a contiguous path out of something like this:
|
|
Prabakaran:
2011-02-15 14:15:08
how is the answer 5 for the second test case?
|
|
piyifan:
2009-09-14 10:34:10
There may be some extra char in the input.
|
Added by: | Yandry Perez |
Date: | 2009-06-23 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO |