Sokoban (storekeeper)

Ve skladišti o ploše 10x10 kostiček se na políčku [sx,sy] nachází skladník a na políčku [bx,by] bedna, kterou je potřeba dopravit na políčko [cx,cy]. Kolem dokola skladiště jsou zdi, zdi-překážky mohou být i na některých políčkách uvnitř skladiště.

Skladník se pohybuje v každém kroku vždy o jedno políčko doleva, doprava, nahoru nebo dolů, je-li před ním (ve směru pohybu) bedna a za ní volné místo, pak při pohybu bednu odstrčí na volné místo a sám se posune na její pozici. Pokud na políčku, kam chce jít, je překážka nebo okraj skladiště, nebo pokud je tam bedna, za kterou je překážka nebo bedna nebo okraj skladiště, pohyb nelze provést.

Napište program, který najde nejmenší počet kroků skladníka potřebný k dopravení bedny na cílové políčko. Pokud bednu na danou cílovou pozici nelze dopravit, vytiskne -1.

Popis vstupu:

Vstup je zadán jako mapa, ve které každý znak určuje obsah políčka:

• (tečka) značí volné políčko X značí překážku S značí skladníka B značí bednu C značí cílové políčko

Příklad:

Vstup:

  ..........
  ..........
  ..........
  ..........
  ..........
  CSB.......
  ..........
  ..........
  ..........
  ..........

Odpovídající výstup:

6