Algorithm
Problem link- https://www.spoj.com/problems/EIGHT/
EIGHT - Eight Directions Crossword
What is an Eight Directions Crossword? It's a filled crossword in which all the words are hidden in eight directions (up, down, left and right and also up-left, down-right etc.) You have to find these hidden words in each crossword.
Ðuro has made an N x N eight-directions-crossword. His crossword is a bit strange: you are given only one word and you have to find it in a crossword. To make things more difficult, you can skip some letters in the crossword while looking for the given word. More precisely, the given word is the subsequence of not necessarily consecutive letters in a row, column or a diagonal of the crossword in one of the eight directions.
Now you discover that, under these conditions, you can read the given word in the crossword in multiple ways. How many?
Input
In the first line of the input there is an integer N (2 = N = 1000), the crossword dimension, followed by space and the given word you are to find. This word has 2-10 letters.
N lines follow, representing the crossword. All letters in the crossword and in the given word are small letters of the English alphabet.
Output
Print the required number of ways. (This number will fit into int64 in Pascal or long long in C/C++.)
Example
input2 aa aa aa
output 12 |
input3 aa aaa aaa aaa
output 56 |
input8 silba siolobba oooaoooo oooboooo aooooooo oboloooo oolooooo oooioooo ooossooo
output 4 |
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
import java.util.*;
import java.math.BigInteger;
class eight
{
public static void main(String args[])
{
int notc;
long c;
Scanner sc=new Scanner(System.in);
notc=sc.nextInt();
long[] k= new long[notc];
try
{
for(int i=0;i<notc;i++)
{
k[i]=sc.nextLong();
c=(k[i]-1)*250+192;
System.out.println(c);
}
}
catch(Exception e)
{
return;
}
}
}
Copy The Code &
Try With Live Editor
Input
aa
aa
Output
Demonstration
SPOJ Solutin-EIGHT Eight Directions Crossword-Solution in C, C++, Java, Python