ZOJ Problem Set - 1536
The labyrinth map represents a checkquered square N*N, with some checks prohibited
for passing. A step in the labyrinth consists of moving from one non-prohibited
check to another non-prohibited check, which has a common side with the given
check. A path is some sequence of steps. It is required to move from check (1,
1) to check (N, N) in exactly K steps, that is, after K-th step appear in check
(N, N). Find the amount of different ways to do it.
1 < N <= 20
The first line of the input file contains two numbers: N and K, separated by one or more spaces. The following N lines with N symbols in each contain the map of the labyrinth beginning with check (1,1). Symbol '0' marks non-prohibited checks and symbol '1' marks prohibited ones.
Process to the end of file.
The output file must contain the result - the amount of possible paths of length K.