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
how is ans 5 for second TC
XXX XXX XXX XX_ _XX
XXX X_X XXX XXX XXX
XX_ XXX _XX XXX XXX
12365478 12369874 12369854 14789652 23654789

Last edit: 2016-03-24 10:41:47
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
Thanks :), Actually I was not counting all unique paths. finally AC :D

Intelligent Idiot: 2013-07-25 11:10:03

@Gitanshu
try this
2
5
XXXXX
XXXXX
XX...
XX...
XX...
8
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX

211
19734

Gitu: 2013-07-25 05:57:50

I think my algorithm is working fine, but getting WA... Is there any tricky test case?
I m applying Backtracking and calculating no. of unique octaves

Last edit: 2013-07-25 05:58:51
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:

xxx
.xx
xxx

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.
Be Careful!


Added by:Yandry Perez
Date:2009-06-23
Time limit:0.275s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO