Travel of alphabets (acm15s_alphabet)

• Problem
• Submit
• Status
• Discussion
• Solution
• Analytics

Time limit:

2000 ms

Memory limit:

256 MB

John Corner demands to generate words from his alphabet table. Each word is composed by traveling of alphabets in four directions (← left, ↑ up, → right, and ↓ down), starting from first alphabet (‘i’) until last alphabet (‘r’). When all words have been created, he would like to know how many words he has. Of course, it is possible to have some duplicated words and he also needs to know how many unique words he got. Please help him to finish these funny tasks.

Moving step explanation:

From the Figure above presented alphabet table that has the 3 row x 4 column.

Case: word length = 1,

Regarding to the alphabet table, take each alphabet starting from ‘i’ (top-left) to ‘r’ (right-down), then there are 12 result words (i c p c h i j k a c m r). Length =1, one alphabet means one word. In this case, there is no traveling in four directions (← ↑ → ↓) since the word is ended by the length (length = 1).

Case: word length = 2,

Take ‘i’ (top-left corner) from the alphabet table. ‘i’ cannot move left or up since there is no adjacent alphabets. ‘i’ can only move right and move down. Then, let move ‘i' to the right, the word will be “ic”. Let move ‘i’ down, the word will be “ih”.

Next step, take another adjacent alphabet ‘c’. ‘c’ can move in ordered left, right and down. The words will be “ci, cp, ci”. He repeats these steps until reaching the last alphabet (‘r’).

Case: word length = 3,

Use the previous travel steps. Thus, let move ‘i’ to the right, the word will be “ic”. (length = 2).

Then, continue to move for the word with length = 3

• move left (from ‘c’) to the last alphabet back to itself. “ic” -> ‘i’.
• CANNOT move up. (There is no an adjacent alphabet above)
• move right (from ‘c’) “ic” -> ‘p’
• move down (from ‘c’) “ic” -> ‘i’

Then, all summarized words starting from the first alphabet will be “ici”, “icp”, “ici”, .... , then, repeat until reaching the last alphabet (‘r’)

Alphabet traveling restriction:

John has been participated ACM ICPC Thailand and he loves it very much. Therefore, he prefers to define “acm” as THREE forbidden alphabets. Any word contains any forbidden alphabets (‘a’ OR ‘c’ OR ‘m’ LOWERCASE only) will be discarded (examples: ici, ahi, and mrk will be rejected)

Remark: When he moves an alphabet to another alphabet, it can be moved back to a previous selected alphabet if it still satisfies the policy (moving four directions, word lengths and forbidden alphabets).

Input

The first line of input contains three unsigned integers: the row “R” (0 < R < 11), the column “C” (0 < C < 11) of the alphabet table and the word length “L” (0 < L < 7) consecutively.

The following R lines represent the alphabet table. Each line is a row containing C characters without space. All given characters are smaller letters.

Output

The first line is an integer calculated from the number of generated words with the length of L, and the second line is an integer calculated from the number of unique words of all words generated.

Editor:

Source: ACM ICPC 2015 Thailand Local Southern