아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Halma

시간 제한1초메모리 제한1024 MB

요약
표시된 말 하나가 주어진 보드에서 한 번의 이동으로 도달할 수 있는 모든 빈 칸을 표시하는 문제다. 이동은 한 칸 걷기 또는 다른 말을 넘는 연속 점프다.
난이도

보통10점 중 5점

유형
BFS, 시뮬레이션, 구현, 그래프
정답자
아직 제출이 없습니다

문제

Halma on traditsiooniliselt kahe või nelja mängija lauamäng, mida mängitakse 8×88 \times 8 või 10×1010 \times 10 ruudust koosneval laual. Detsembris, kui Jõuluvanal on kiired päevad, mängib Jõulumemm ühe mängija varianti. Vahelduse suurendamiseks kasutab ta erinevaid ristkülikulisi mängulaudu.

Mängu alguses on mängija nupud laua ühes nurgas oleval stardialal ja eesmärk on viia need diagonaalis vastasnurka finišialale. Selleks võib teha kahesuguseid käike:

  • Sammuks nimetame nupu liigutamist tühjale naaberruudule samas reas või samas veerus, nagu näidatud alloleval joonisel vasakul. Sammukäigul võib teha ainult ühe sammu.
  • Hüppeks nimetame nupu liigutamist üle naaberruudul oleva nupu vahetult selle taga olevale tühjale ruudule samas reas või samas veerus. Hüpata võib ainult üle ühe nupu, nagu näidatud alloleval joonisel keskel (rohelise noole suunas saab hüpata, punase suunas ei saa). Erinevalt kabest üle teise nupu hüppamine teist nuppu kuidagi ei mõjuta. Hüppekäik võib koosneda ühest või mitmest järjestikusest hüppest sama nupuga, nagu näidatud alloleval joonisel paremal. Hüpete jada ei pea olema maksimaalse pikkusega: mängija võib käigu oma soovi kohaselt igal hetkel lõpetada, isegi kui tal oleks võimalik veel edasi hüpata.

Kirjutada programm, mis saab mänguseisu ja leiab sellel kõik ruudud, millele antud nupp ühe käiguga jõuda võib.

입력

Sisendi esimesel real on mängulaua ridade arv NN ja veergude arv MM (3≤N,M≤1003 \le N, M \le 100).

Järgmisel NN real on igaühel täpselt MM märki, kus punkt '.' tähistab tühja ruutu, trellimärk '#' uuritavat nuppu ja tärn '*' muud nuppu.

출력

Väljastada täpselt NN rida, igale reale täpselt MM märki: sisendis antud mängulaud, kus plussidega '+' on märgitud need ruudud, kuhu uuritav nupp ühe käiguga jõuda võib.

예제1

  1. 예제 1

    입력
    6 7
.......
.......
..*#*..
...*.*.
...*...
.......
    예상 출력
    .......
...+...
.+*#*+.
...*.*.
...*.+.
.......