Gotta Catch them all
All submissions for this problem are available.Palet town has P areas. Each area can be thought of as a 2xN grid where each cell represents a Pokemon. Every cell in the area contains a single lowercase character denoting the first character of the pokemon corresponding to that cell.
You can catch a pokemon by moving from one place to another. But you can only move by 1 step from each cell only in either horizontal or in vertical direction. Diagonal movement is forbidden.
Ash wants to catch all the pokemons in Palet town. He can start his adventure by catching any pokemon and will stop when he has collected each pokemon at least once. Moreover Ash wants to defeat Gary therefore he plans to collect the pokemons in the minimum time.
After catching pokemons from each area, Ash forms a string from the initials of pokemons he caught. How many different strings can he form in each area ?
Input Format :
The first line contains a single integer,P , denoting the number of areas. The subsequent lines describe each area over the following three lines:
The first line contains an integer,N , denoting the number of columns in the area.
Each of the next two lines contains a string,S , of length N denoting the characters for the first and second row of the area.
Output Format :
For each area, print the number of distinct strings Ash can form on a new line.
Sample Input :
Sample Output :
In test case 2, eight different strings can be formed (abdbad, badabd , dababd, dabdba, bdbada,dbabad, adabdb and dbadab), so we print 8 on a new line.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions