CSES - Sokkelo
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Annettuna on kuvaus n×mn \times m -sokkelosta, joka muodostuu lattia- ja seinäruuduista. Lisäksi sokkelossa on lähtöruutu ja maaliruutu.

Robotti liikkuu sokkelossa kk askelta alkaen lähtöruudusta. Robotti voi liikkua vasemmalle, oikealle, ylöspäin ja alaspäin, mutta vain ruutuihin, joissa ei ole seinää, eikä ruudukon ulkopuolelle.

Joka askeleella robotti valitsee satunnaisesti, mihin suuntaan se liikkuu, niiden viereisten ruutujen joukosta, joihin se voi liikkua. Jokaisen ruudun todennäköisyys tulla valituksi on sama.

Tehtäväsi on laskea todennäköisyys, että robotti on maaliruudussa tasan kk askeleen jälkeen.

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua nn, mm ja kk, jotka ilmaisevat sokkelon koon ja askelten määrän.

Sitten syötteessä on nn riviä, joista jokaisella on mm merkkiä. Nämä rivit kuvaavat sokkelon. Mahdolliset merkit ovat # (seinä), . (lattia), A (lähtö) ja B (maali). Merkkejä A ja B on molempia tasan yksi.

Tuloste

Tulosta todennäköisyys, että robotti päätyy maaliruutuun kk askeleen jälkeen.

Tulosta vastaus pyöristettynä niin, että siinä on tasan 6 desimaalia.

Rajat

  • 1n,m101 \le n,m \le 10
  • 1k1001 \le k \le 100

Esimerkki

Syöte:

3 4 3
#A##
#.##
B..#

Tuloste:

0.166667