Нужно провести главного героя из одной точки игрового поля в другую кратчайшим путем, не заходя на препятствия. Игровое поле представляет собой тор.
Тор в нашем случае - бублик, состоящий из N×M клеток. Из каждой клетки всегда можно перейти за 1 ход в любом из 4ех направлений. Например из клетки [0,0] можно попасть в клетки [M−1,0], [N−1,0], [1,0] и [0,1].
Постройте кратчайший путь из точки старта в точку финиша, но не заходите на препятствия. Если путей несколько - подойдет любой. Если пути нет, выведите -1.
В первой строке целое число N (0 < N ≤1 03) и M (0 < M ≤ 103) - количество строк и столбцов на торе. Во второй 4 числа Sn , Sm , Fn , Fm - координаты точки старта и точки финиша. 0 ≤S n,F n < N ; 0 ≤S m,Fm < M. Дальше идет описание клеток поля. N строк по M чисел в каждой. Число в клетке может быть либо 0 – свободна, либо 1 – препятствие.
Гарантируется, что поле состоит хотя бы из 2х клеток, точка старта и точка финиша не совпадают и являются клетками без препятствий.
Выведите цепочку команд для главного героя в формате: S – движение на клетку вниз, W – влево, N – вверх, E – вправо.
Если пути нет, выведите -1.
Пример 1
Ввод
4 4
0 1 3 2
1 0 0 0
1 0 1 0
0 0 0 0
0 0 0 0
Вывод
EN
Пример 2
Ввод
10 10
1 0 8 8
1 0 1 0 0 0 0 0 0 1
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 1 0 0
0 0 1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
Вывод
SSSWWSSESESEEEEEEEE
Пример 3
Ввод
4 4
0 3 2 1
1 1 1 0
1 1 1 1
1 0 1 1
1 1 1 1
Вывод-1
Пример 4
Ввод
1 12
0 0 0 6
0 0 0 0 0 0 0 0 0 0 0 0
Вывод
WWWWWW
Решение
import kotlin.io.*
import kotlin.math.abs
fun main() {
var w: String = null.toString()
var f1: Int = 0
var f2: Int = 0
var f3: Int = 0
var f4: Int = 0
var o: Int = 0
var str1: String = null.toString()
var str2: String = null.toString()
var str3: String = null.toString()
var str4: String = null.toString()
var lastIndex1: Int = 1000
var lastIndex2: Int = 1000
var lastIndex3: Int = 1000
var lastIndex4: Int = 1000 //println("Введите число строк n(0<n<=10^3) и число столбцов m(0<m<=10^3)")
val str = Array(1, { r -> readLine().toString() })
var (n, m) = str[0]!!.split(' ')
// print(n.toInt() + m.toInt())
// println("Введите координаты точек старта и финиша 0<=Sn,Fn<n; 0<=Sm,Fm<m") var tor = Array(1, { z -> readLine().toString() })
var (x, y, x1, y1) = tor[0]!!.split(' ')
//println("$x+$y+$x1+$y1")
// println("Введите построчно описание клеток поля") var torus = Array(n.toInt(), { c -> readLine().toString() })
// Создаём двумерный массив var torus2M: Array<Array<Int>> = Array(n.toInt(), {
Array(m.toInt(), { 0 }) })
for (i in 0..n.toInt() - 1) {
var v = torus[i].split(' ').toTypedArray()
var array = arrayOf<Int>()
for (j in 0..m.toInt() - 1) {
array += v[j].toInt()
}
torus2M[i] = array
}
var route = arrayOf<String>()
// Вперед по горизонтали var x2: Int = x.toInt()
var y2: Int = y.toInt()
var w1: String = null.toString()
var w2: String = null.toString()
var w3: String = null.toString()
var w4: String = null.toString()
fun forwardG(w: String) {
do {
if (w == "E") {
var q = 1
do {
var tx = x2
var ty = y2 + q
if (ty > m.toInt() - 1) {
ty = (y2 + q) - m.toInt()
} //вправо if (torus2M[tx][ty] != 1) {
route += "E"
// Проверка на окончание if (tx == x1.toInt() && ty == y1.toInt()) {
x2 = tx
y2 = ty
return
} // проверка на поворот if (ty == y1.toInt()) {
y2 = ty
return
}
} else {
y2 = ty - 1
if (y2 < 0) {
y2 = n.toInt() - 1
}
return
}
q++
} while (q != m.toInt())
// влево } else if (w == "W") {
var q = 1
do {
var tx = x2
var ty1 = y2 - q
if (ty1 < 0) {
ty1 = m.toInt() - abs(y2 - q).toInt()
}
//обход по горизонтали вправо fun detourGR(w: String) { // Проверка на окончание if (x2 == x1.toInt() && y2 == y1.toInt()) {
return
}
if (w == "E") {
do {
var h = 0
var h1 = 0
var p = 0
var p1 = 0
var rou = arrayOf<String>()
var rou1 = arrayOf<String>()
var rou2 = arrayOf<String>()
var rou3 = arrayOf<String>()
for (e in 1..n.toInt() / 2) {
rou += "S"
rou1 += "N"
var tx = x2 + e
if (tx > n.toInt() - 1) {
tx = (x2 + e) - n.toInt()
}
var tx1 = x2 - e
if (tx1 < 0) {
tx1 = n.toInt() - abs(x2 - e).toInt()
}
var tx2 = tx - 1
if (tx2 < 0) {
tx2 = n.toInt() - abs(tx - e).toInt()
}
var tx3 = tx1 + 1
if (tx3 > n.toInt() - 1) {
tx3 = (tx1 + e) - n.toInt()
}
var ty = y2 + 1
if (ty > n.toInt() - 1) {
ty = (y2 + 1) - n.toInt()
}
var ty3 = ty + 1
if (ty3 > m.toInt() - 1) {
ty3 = 0
}
if (torus2M[tx][y2] != 1) {
if (torus2M[tx][y2] != 1 && torus2M[tx][ty] != 1 && torus2M[tx][ty3] != 1 && torus2M[tx2][ty3] != 1 && h != 1) {
for (i in rou) {
route += "S"
}
route += "EEN"
x2 = tx2
y2 = ty3
return
}
} else {
x2 = tx - e
if (x2 < 0) {
x2 = n.toInt() - abs(tx - e).toInt()
}
h = 1
}
if (torus2M[tx1][y2] != 1) {
if (torus2M[tx1][y2] != 1 && torus2M[tx1][ty] != 1 && torus2M[tx1][ty3] != 1 && torus2M[tx3][ty3] != 1 && p != 1) {
for (i in rou1) {
route += "N"
}
route += "EES"
x2 = tx3
y2 = ty3
return
}
} else {
x2 = tx1 + e
if (x2 > n.toInt() - 1) {
x2 = (tx1 + e) - n.toInt()
}
p = 1
}
if (e == n.toInt() / 2 || h == 1 && p == 1) {
break
}
}
for (e in 1..n.toInt() / 2) {
rou2 += "S"
rou3 += "N"
var tx = x2 + e
if (tx > n.toInt() - 1) {
tx = (x2 + e) - n.toInt()
}
var tx1 = x2 - e
if (tx1 < 0) {
tx1 = n.toInt() - abs(x2 - e).toInt()
}
var ty = y2 + 1
if (ty > n.toInt() - 1) {
ty = (y2 + 1) - n.toInt()
}
if (torus2M[tx][y2] != 1) {
if (torus2M[tx][y2] != 1 && torus2M[tx][ty] != 1 && h1 != 1) {
for (i in rou2) {
route += "S"
}
route += "E"
x2 = tx
y2 = ty
break
}
} else {
x2 = tx - e
if (x2 < 0) {
x2 = n.toInt() - abs(tx - e).toInt()
}
h1 = 1
}
if (torus2M[tx1][y2] != 1) {
if (torus2M[tx1][y2] != 1 && torus2M[tx1][ty] != 1 && p1 != 1) {
for (i in rou3) {
route += "N"
}
route += "E"
x2 = tx1
y2 = ty
break
}
} else {
p1 = 1
x2 = tx1 + e
if (x2 > n.toInt() - 1) {
x2 = (tx1 + e) - n.toInt()
}
if (h1 == 1 && p1 == 1) {
w2 = "N"
}
}
// обход по вертикали вниз fun detourVD(w: String) { // Проверка на окончание if (x2 == x1.toInt() && y2 == y1.toInt()) {
return
}
if (w == "S") {
do {
var h = 0
var h1 = 0
var p = 0
var p1 = 0
var rou = arrayOf<String>()
var rou1 = arrayOf<String>()
var rou2 = arrayOf<String>()
var rou3 = arrayOf<String>()
for (e in 1..m.toInt() / 2) {
rou += "E"
rou1 += "W"
var tx = x2 + 1
if (tx > n.toInt() - 1) {
tx = (x2 + 1) - n.toInt()
}
var tx2 = tx + 1
if (tx2 > n.toInt() - 1) {
tx2 = 0
}
var ty = y2 + e
if (ty > n.toInt() - 1) {
ty = (y2 + e) - n.toInt()
}
var ty1 = y2 - e
if (ty1 < 0) {
ty1 = m.toInt() - abs(y2 - e).toInt()
}
var ty2 = ty - 1
if (ty2 < 0) {
ty2 = m.toInt() - abs(ty - e).toInt()
}
var ty3 = ty1 + 1
if (ty3 > n.toInt() - 1) {
ty3 = (ty1 + e) - n.toInt()
}
if (torus2M[x2][ty] != 1) {
if (torus2M[x2][ty] != 1 && torus2M[tx][ty] != 1 && torus2M[tx2][ty] != 1 && torus2M[tx2][ty2] != 1 && h != 1) {
for (i in rou) {
route += "E"
}
route += "SSW"
y2 = ty2
x2 = tx2
return
}
} else {
y2 = ty - e
if (y2 < 0) {
y2 = m.toInt() - abs(ty - e).toInt()
}
h = 1
}
if (torus2M[x2][ty1] != 1) {
if (torus2M[x2][ty1] != 1 && torus2M[tx][ty1] != 1 && torus2M[tx2][ty1] != 1 && torus2M[tx2][ty3] != 1 && p != 1) {
for (i in rou1) {
route += "W"
}
route += "SSE"
y2 = ty3
x2 = tx2
return
}
} else {
y2 = ty1 + e
if (y2 > n.toInt() - 1) {
y2 = (ty1 + e) - n.toInt()
}
p = 1
}
if (e == m.toInt() / 2 || h == 1 && p == 1) {
break
}
}
for (e in 1..m.toInt() / 2) {
rou2 += "E"
rou3 += "W"
// обход по вертикали вверх fun detourV(w: String) { // Проверка на окончание if (x2 == x1.toInt() && y2 == y1.toInt()) {
return
}
if (w == "N") {
do {
var h = 0
var h1 = 0
var p = 0
var p1 = 0
var rou = arrayOf<String>()
var rou1 = arrayOf<String>()
var rou2 = arrayOf<String>()
var rou3 = arrayOf<String>()
for (e in 1..m.toInt() / 2) {
rou += "W"
rou1 += "E"
var tx1 = x2 - 1
if (tx1 < 0) {
tx1 = n.toInt() - 1
}
var tx3 = tx1 - 1
if (tx3 < 0) {
tx3 = n.toInt() - 1
}
var ty = y2 + e
if (ty > n.toInt() - 1) {
ty = (y2 + e) - n.toInt()
}
var ty1 = y2 - e
if (ty1 < 0) {
ty1 = m.toInt() - abs(y2 - e).toInt()
}
var ty2 = ty - 1
if (ty2 < 0) {
ty2 = m.toInt() - abs(ty - e).toInt()
}
var ty3 = ty1 + 1
if (ty3 > n.toInt() - 1) {
ty3 = (ty1 + e) - n.toInt()
}
if (torus2M[x2][ty1] != 1) {
if (torus2M[x2][ty1] != 1 && torus2M[tx1][ty1] != 1 && torus2M[tx3][ty1] != 1 && torus2M[tx3][ty3] != 1 && h != 1) {
for (i in rou) {
route += "W"
}
route += "NNE"
y2 = ty3
x2 = tx3
return
}
} else {
y2 = ty1 + e
if (y2 > n.toInt() - 1) {
y2 = (ty1 + e) - n.toInt()
}
h = 1
}
if (torus2M[x2][ty] != 1) {
if (torus2M[x2][ty] != 1 && torus2M[tx1][ty] != 1 && torus2M[tx3][ty] != 1 && torus2M[tx3][ty2] != 1 && p != 1) {
for (i in rou1) {
route += "E"
}
route += "NNW"
y2 = ty2
x2 = tx3
return
}
} else {
y2 = ty - e
if (y2 < 0) {
y2 = m.toInt() - abs(ty - e).toInt()
}
p = 1
}
if (e == m.toInt() / 2 || h == 1 && p == 1) {
break
}
}
for (e in 1..m.toInt() / 2) {
rou2 += "W"
rou3 += "E"
var tx1 = x2 - 1
if (tx1 < 0) {
tx1 = n.toInt() - abs(x2 - 1).toInt()
}
var ty1 = y2 - e
if (ty1 < 0) {
ty1 = m.toInt() - abs(y2 - e).toInt()
}
var ty = y2 + e
if (ty > n.toInt() - 1) {
ty = (y2 + e) - n.toInt()
}
if (torus2M[x2][ty1] != 1) {
if (torus2M[x2][ty1] != 1 && torus2M[tx1][ty1] != 1 && h1 != 1) {
for (i in rou2) {
route += "W"
}
route += "N"
y2 = ty1
x2 = tx1
break
}
} else {
y2 = ty1 + e
if (y2 > n.toInt() - 1) {
y2 = (ty1 + e) - n.toInt()
}
h1 = 1
}
if (torus2M[x2][ty] != 1) {
if (torus2M[x2][ty] != 1 && torus2M[tx1][ty] != 1 && p1 != 1) {
for (i in rou3) {
route += "E"
}
route += "N"
y2 = ty
x2 = tx1
break
}
} else {
p1 = 1
y2 = ty - e
if (y2 < 0) {
y2 = m.toInt() - abs(ty - e).toInt()
}
if (h1 == 1 && p1 == 1) {
w4 = "W"
}
}
if (e >= m.toInt() / 2 - 1 || h1 == 1 && p1 == 1) {
w4 = "W"
f4 = 1
if (f1 == 1 && f2 == 1 && f3 == 1 && f4 == 1) { println("1")
return
}
return
}
}
do { // направление if (w == "null") {
w = "E"
} //движение по направлениям:
// вправо do { // Проверка на окончание if (x2 == x1.toInt() && y2 == y1.toInt()) {
break
}
if (w == "E") {
forwardG(w)
if (f1 == 1 && f2 == 1 && f3 == 1 && f4 == 1) {
return
} // проверка на окончание if (x2 == x1.toInt() && y2 == y1.toInt()) {
break
} // проверка на поворот if (y2 == y1.toInt()) {
if ((x1.toInt() - x.toInt()) >= n.toInt() / 2 && f4 != 1) {
w = "N"
} else if (f3 != 1) {
w = "S"
}
} // обход var y4 = y2 + 1
if (y4 > m.toInt() - 1) {
y4 = 0
}
if (w == "E" && torus2M[x2][y4] == 1) {
if (y2 < 0) {
y2 = m.toInt() - 1
}
detourGR(w)
if (f1 == 1 && f2 == 1 && f3 == 1 && f4 == 1) {
return
}
if (w2 != null.toString()) {
w = w2
} // проверка на окончание if (x2 == x1.toInt() && y2 == y1.toInt()) {
break
} // поворот if (y2 == y1.toInt()) {
if ((x1.toInt() - x.toInt()) >= n.toInt() / 2 && f4 != 1) {
for (i in 1..n.toInt() / 2) {
var u = x2 + i
if (u > n.toInt() - 1) {
u = (x2 + i) - n.toInt()
}
if (torus2M[x2][u] == 1) {
break
} else w = "N"
}
if (f3 != 1) {
w = "S"
} else w = "W"
} else if (f3 != 1) {
w = "S"
} else w = "W"
}
}
}
// влево if (w == "W") {
forwardG(w)
if (f1 == 1 && f2 == 1 && f3 == 1 && f4 == 1) {
return
} // проверка на окончание if (x2 == x1.toInt() && y2 == y1.toInt()) {
break
} // поворот if (y2 == y1.toInt()) {
if ((x1.toInt() - x.toInt()) >= n.toInt() / 2 && f4 != 1) {
w = "N"
} else if (f3 != 1) {
w = "S"
}
} // обход var y3 = y2 - 1
if (y3 < 0) {
y3 = m.toInt() - 1
}
if (w == "W" && torus2M[x2][y3] == 1) {
if (y2 > m.toInt() - 1) {
y2 = 0
}
detourGL(w)
if (f1 == 1 && f2 == 1 && f3 == 1 && f4 == 1) {
return
}
if (w1 != null.toString()) {
w = w1
} // проверка на окончание if (x2 == x1.toInt() && y2 == y1.toInt()) {
break
} // поворот if (y2 == y1.toInt()) {
if ((x1.toInt() - x.toInt()) >= n.toInt() / 2 && f4 != 1) {
for (i in 1..n.toInt() / 2) {
var u = x2 - i
if (u < 0) {
u = n.toInt() - abs(x2 - i).toInt()
}
if (torus2M[x2][u] == 1) {
break
} else w = "N"
}
if (f3 != 1) {
w = "S"
} else w = "E"
} else if (f3 != 1) {
w = "S"
} else w = "E"
}
}
}
// Вверх if (w == "N") {
forwardV(w)
if (f1 == 1 && f2 == 1 && f3 == 1 && f4 == 1) {
return
} // проверка на окончание if (x2 == x1.toInt() && y2 == y1.toInt()) {
break
} // поворот if (x2 == x1.toInt()) {
if ((y1.toInt() - y.toInt()) <= m.toInt() / 2 && f2 != 1) {
w = "E"
} else if (f1 != 1) {
w = "W"
}
} // обход var x3 = x2 - 1
if (x3 < 0) {
x3 = n.toInt() - 1
}
if (w == "N" && torus2M[x3][y2] == 1) {
if (x2 > n.toInt() - 1) {
x2 = 0
}
detourV(w)
if (f1 == 1 && f2 == 1 && f3 == 1 && f4 == 1) {
return
}
if (w4 != null.toString()) {
w = w4
} // проверка на окончание if (x2 == x1.toInt() && y2 == y1.toInt()) {
break
} // поворот if (x2 == x1.toInt()) {
if ((y1.toInt() - y.toInt()) >= m.toInt() / 2 && f1 != 1) {
for (i in 1..n.toInt() / 2) {
var u = y2 + i
if (u > m.toInt() - 1) {
u = (y2 + i) - n.toInt()
}
if (torus2M[x2][u] == 1 || f1 == 1) {
break
} else w = "W"
}
if (f2 != 1) {
w = "E"
} else w = "S"
} else if (f2 != 1) {
w = "E"
} else w = "S"
}
}
}
if ((y1.toInt() - y.toInt()) >= m.toInt() / 2 && f1 != 1) {
w = "W"
} else if (f2 != 1) {
w = "E"
}
} // обход var x4 = x2 + 1
if (x4 > n.toInt() - 1) {
x4 = 0
}
if (w == "S" && torus2M[x4][y2] == 1) {
if (x2 < 0) {
x2 = n.toInt() - 1
}
detourVD(w)
if (f1 == 1 && f2 == 1 && f3 == 1 && f4 == 1) {
return
}
if (w3 != null.toString()) {
w = w3
} // проверка на окончание if (x2 == x1.toInt() && y2 == y1.toInt()) {
break
} // поворот if (x2 == x1.toInt()) {
if ((y1.toInt() - y.toInt()) >= m.toInt() / 2 && f1
!= 1) {
for (i in 1..n.toInt() / 2) {
var u = y2 - i
if (u < 0) {
u = m.toInt() - abs(y2 - i).toInt()
}
if (torus2M[x2][u] == 1 || f1 == 1) {
break
} else w = "W"
}
if (f2 != 1) {
w = "E"
} else w = "N"
} else if (f2 != 1) {
w = "E"
} else w = "N"
}
}
}
} while (x2 != x1.toInt() || y2 != y1.toInt())
if (f1 == 1 && f2 == 1 && f3 == 1 && f4 == 1) {
return
}
x2 = x.toInt()
y2 = y.toInt()
o += 1
if (o == 1) {
str1 = ""
route.onEach { str1 += it } // println(str1) w = "W"
lastIndex1 = str1.lastIndex
// println(lastIndex1) route = arrayOf<String>()
}
if (o == 2) {
str2 = ""
route.onEach { str2 += it } // println(str2) w = "N"
lastIndex2 = str2.lastIndex
// println(lastIndex2) route = arrayOf<String>()
} else if (o == 3) {
str3 = ""
route.onEach { str3 += it } // println(str3) w = "S"
lastIndex3 = str3.lastIndex
// println(lastIndex3) route = arrayOf<String>()
} else if (o == 4) {
str4 = ""
route.onEach { str4 += it } // println(str4) lastIndex4 = str4.lastIndex
// println(lastIndex4) }
} while (str1 == null.toString() && f2 != 1 || str2 == null.toString() && f1 != 1 || str3 == null.toString() && f4 != 1 || str4 == null.toString() && f3 != 1)
if (lastIndex1 <= lastIndex2 && lastIndex1 <= lastIndex3 && lastIndex1 <= lastIndex4 ){ println(str1)
}
if (lastIndex2 <= lastIndex1 && lastIndex2 <= lastIndex3 && lastIndex2 <= lastIndex4 ){ println(str2)
}
if (lastIndex3 <= lastIndex1 && lastIndex3 <= lastIndex2 && lastIndex3 <= lastIndex4 ){ println(str3)
}
if (lastIndex4 <= lastIndex1 && lastIndex4 <= lastIndex2 &&
lastIndex4 <= lastIndex3 ){ println(str4)
}
}
Подписки НЕТ!
Поиск необходимой информации осуществляется в разделах Главного меню по ссылкам.
Уважая чужой опыт, считаю ОБЯЗАТЕЛЬНЫМ наличие «Обратной связи»:
Права на материалы, размещенные на сайте, принадлежат Автору.
Все права защищены и охраняются законом.
При использовании материалов с сайта ссылка на него обязательна.
