Escape from the board P18760


Statement
 

pdf   zip

html

Consider an n × m chess board. Initially you are at the lower-right corner, that is, at the position (n − 1, m − 1). Your goal is to get out of the board. There are some prohibited cells, marked with asterisks. The allowed cells have a ‘K’ or an ‘N’. When you are on a ‘K’, you can move like a chess king. When you are on an ‘N’, you can move like a chess knight. Moreover, you cannot make any move that increments the current row or column. In how many ways can you leave the board?

Input

Input consists of several cases. Every case begins with two natural numbers n and m, both between 1 and 12. Follow n lines with m characters each, which can be an asterisk, a ‘K’ or an ‘N’. The lower-right corner never has an asterisk.

Output

For every case, print the number of ways to leave the board. This number is always smaller than 109.

Public test cases
  • Input

    1 2
    *K
    
    1 2
    NK
    
    2 2
    **
    *K
    
    3 3
    KK*
    K**
    **N
    
    3 7
    NK***KK
    KK*NKKK
    KKKKKKN
    

    Output

    2
    4
    0
    10
    7
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++