Разпръскване на коня


Submit solution



Points:100 (partial)
Time limit:0.2s
Java0.5s
Memory limit:32M
Java32M
Author:

Tags
Graphs
Difficulty
Intermediate

Дадена е матрица N x M и стартова позиция. Вашата задача е да обходите матрицата, използвайки движения на кон от играта шах и маркирайки от къде сте минали.

Обхождането се случва по следния начин:

  1. На стартовата позиция е числото 1
  2. Започвайки от дадена клетка със стойност V, на всички клетки, до които може да се стигне с движение на кон и по които още не е минато, се записва стойност V+1.
  3. След като запишете всички стойности V+1, отивате на всяка от тези клетки и повтаряте същото

Вход

Входните данни ще бъдат прочитани от конзолата.

  • Първият ред от входа съдържа числото N – броя на редовете в матрицата
  • Вторият ред от входа съдържа числото M – броя на колоните в матрицата
  • Третият ред от входа съдържа числото R – редът, от който започва коня
  • Четвъртият ред от входа съдържа числото C – колоната, от която започва коня
  • Редовете и колоните се номерират от 0, т.е. клетката в горния ляв ъгъл е с позиция (0, 0), а клетката в долния десен ъгъл е с позиция (N-1, M-1)

Входът на програмата ще бъде валиден винаги и в описания формат. Няма нужда да бъде проверяван изрично.

Изход

Изходът от програмата трябва да бъде изпечатан на конзолата.

  • Изпишат всички клетки на колоната от матрицата, която с номер M/2 (при целочислено деление), като всяка клетка е на нов ред
    • Ако конят не е минал през някоя от позициите, принтирайте 0 на тази позиция.

Ограничения

  • N е в интервала от 5 до 1500, включително.
  • M е в интервала от 5 до 1000, включително

Примерни тестове

Вход

6
7
3
4

Изход

3
2
3
4
3
2

Обяснение

Получава се матрицата


Comments

There are no comments at the moment.