Кратчайший путь рыцаря на шахматной доске
Я готовился к предстоящему соревнованию по программированию, и я наткнулся на вопрос, который меня просто озадачил. Тем не менее, я чувствую, что это концепция, которую я должен изучить сейчас, а не скрещивать пальцы, что она никогда не подходит.
В основном это касается фигуры рыцаря на шахматной доске. Вам дают два входа: начальное местоположение и конечное местоположение. Цель состоит в том, чтобы затем рассчитать и распечатать кратчайший путь, по которому рыцарь может добраться до места назначения.
Я никогда не имел дела с кратчайшим путём, и даже не знаю, с чего начать. Какую логику я использую, чтобы заняться этим?
PS Если это имеет какое-либо отношение, они хотят, чтобы вы дополнили обычные ходы коня, также позволив ему перейти к четырем углам квадрата, образованного (потенциально) восемью ходами, которые может сделать рыцарь, учитывая, что центр квадрата расположение рыцаря.
19 ответов
Здесь у вас есть график, где все доступные ходы связаны (значение =1), а недоступные ходы отключены (значение =0), разреженная матрица будет выглядеть так:
(a1,b3)=1,
(a1,c2)=1,
.....
И кратчайший путь из двух точек на графике можно найти с помощью http://en.wikipedia.org/wiki/Dijkstra's_algorithm
Псевдокод с википедии-страницы:
function Dijkstra(Graph, source):
for each vertex v in Graph: // Initializations
dist[v] := infinity // Unknown distance function from source to v
previous[v] := undefined // Previous node in optimal path from source
dist[source] := 0 // Distance from source to source
Q := the set of all nodes in Graph
// All nodes in the graph are unoptimized - thus are in Q
while Q is not empty: // The main loop
u := vertex in Q with smallest dist[]
if dist[u] = infinity:
break // all remaining vertices are inaccessible from source
remove u from Q
for each neighbor v of u: // where v has not yet been removed from Q.
alt := dist[u] + dist_between(u, v)
if alt < dist[v]: // Relax (u,v,a)
dist[v] := alt
previous[v] := u
return dist[]
РЕДАКТИРОВАТЬ:
- как сказал придурок, использование http://en.wikipedia.org/wiki/A*_algorithm может быть быстрее.
- Самый быстрый способ - это предварительно рассчитать все расстояния и сохранить их в полной матрице 8x8. ну, я бы назвал это обманом и работает только потому, что проблема небольшая. Но иногда соревнования проверят, насколько быстро работает ваша программа.
- Суть в том, что если вы готовитесь к соревнованию по программированию, вы должны знать общие алгоритмы, в том числе и Дейкстры. Хорошей отправной точкой является чтение
Introduction to AlgorithmsISBN 0-262-03384-4. Или вы можете попробовать википедию, http://en.wikipedia.org/wiki/List_of_algorithms
РЕДАКТИРОВАТЬ: см. Ответ Саймона, где он исправил формулу, представленную здесь.
На самом деле есть формула O(1)
Это изображение, которое я сделал, чтобы визуализировать его (квадраты, которые рыцарь может достичь на N-м ходу, окрашены в тот же цвет).
Можете ли вы заметить образец здесь?
Хотя мы можем видеть шаблон, действительно трудно найти функцию f( x , y ) который возвращает количество ходов, необходимое для перехода от квадрата ( 0 , 0 ) в квадрат ( x , y )
Но вот формула, которая работает, когда 0 <= y <= x
int f( int x , int y )
{
int delta = x - y;
if( y > delta )
return 2 * ( ( y - delta ) / 3 ) + delta;
else
return delta - 2 * ( ( delta - y ) / 4 );
}
Примечание: этот вопрос был задан в первый день SACO 2007
И решения здесь
Вот правильное решение O(1), но для случая, когда конь движется только как шахматный конь и на бесконечной шахматной доске:
https://jsfiddle.net/graemian/5qgvr1ba/11/
Ключом к обнаружению этого является замечание паттернов, которые появляются, когда вы рисуете доску. На диаграмме ниже число в квадрате - это минимальное количество ходов, необходимое для достижения этого квадрата (вы можете использовать поиск в ширину, чтобы найти это):
Поскольку решение симметрично по осям и диагоналям, я нарисовал только случай x >= 0 и y >= x.
Нижний левый блок - это начальная позиция, а числа в блоках представляют минимальное количество ходов для достижения этих блоков.
Есть 3 модели, чтобы заметить:
- Приращения синих вертикальных групп по 4
- "Первичные" красные диагонали (они идут слева направо, как обратный слеш)
- "Вторичные" зеленые диагонали (такая же ориентация, как красная)
(Убедитесь, что вы видите оба набора диагоналей сверху-слева-вниз-справа. Они имеют постоянное число ходов. Слева внизу справа и справа диагонали намного сложнее.)
Вы можете получить формулы для каждого. Желтые блоки - это особые случаи. Таким образом, решение становится:
function getMoveCountO1(x, y) {
var newXY = simplifyBySymmetry(x, y);
x = newXY.x;
y = newXY.y;
var specialMoveCount = getSpecialCaseMoveCount(x ,y);
if (specialMoveCount !== undefined)
return specialMoveCount;
else if (isVerticalCase(x, y))
return getVerticalCaseMoveCount(x ,y);
else if (isPrimaryDiagonalCase(x, y))
return getPrimaryDiagonalCaseMoveCount(x ,y);
else if (isSecondaryDiagonalCase(x, y))
return getSecondaryDiagonalCaseMoveCount(x ,y);
}
самое сложное - это вертикальные группы:
function isVerticalCase(x, y) {
return y >= 2 * x;
}
function getVerticalCaseMoveCount(x, y) {
var normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y);
var groupIndex = Math.floor( normalizedHeight / 4);
var groupStartMoveCount = groupIndex * 2 + x;
return groupStartMoveCount + getIndexInVerticalGroup(x, y);
}
function getIndexInVerticalGroup(x, y) {
return getNormalizedHeightForVerticalGroupCase(x, y) % 4;
}
function getYOffsetForVerticalGroupCase(x) {
return x * 2;
}
function getNormalizedHeightForVerticalGroupCase(x, y) {
return y - getYOffsetForVerticalGroupCase(x);
}
Смотрите скрипку для других случаев.
Может быть, есть более простые или более элегантные модели, которые я пропустил? Если это так, я хотел бы увидеть их. В частности, я заметил некоторые диагональные узоры в синих вертикальных корпусах, но я их не исследовал. Несмотря на это, это решение все еще удовлетворяет ограничению O(1).
Очень интересная проблема, с которой я столкнулся недавно. После поиска некоторых решений я попытался восстановить аналитическую формулу (O(1) time and space complexity) дано на SACO 2007 День 1 решения.
Прежде всего я хочу поблагодарить Graeme Pyle за очень приятную визуализацию, которая помогла мне исправить формулу.
По какой-то причине (возможно, для упрощения или красоты или просто по ошибке) они переехали minus войти в floor оператор, в результате они получили неправильную формулу floor(-a) != -floor(a) for any a,
Вот правильная аналитическая формула:
var delta = x-y;
if (y > delta) {
return delta - 2*Math.floor((delta-y)/3);
} else {
return delta - 2*Math.floor((delta-y)/4);
}
Формула работает для всех пар (x,y) (после применения осей и диагональной симметрии), кроме (1,0) и (2,2) угловых случаев, которые не соответствуют шаблону и жестко закодированы в следующем фрагменте:
function distance(x,y){
// axes symmetry
x = Math.abs(x);
y = Math.abs(y);
// diagonal symmetry
if (x < y) {
t = x;x = y; y = t;
}
// 2 corner cases
if(x==1 && y == 0){
return 3;
}
if(x==2 && y == 2){
return 4;
}
// main formula
var delta = x-y;
if(y>delta){
return delta - 2*Math.floor((delta-y)/3);
}
else{
return delta - 2*Math.floor((delta-y)/4);
}
}
$body = $("body");
var html = "";
for (var y = 20; y >= 0; y--){
html += '<tr>';
for (var x = 0; x <= 20; x++){
html += '<td style="width:20px; border: 1px solid #cecece" id="'+x+'_'+y+'">'+distance(x,y)+'</td>';
}
html += '</tr>';
}
html = '<table>'+html+'</table>';
$body.append(html);<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>Примечание: jQuery используется только для иллюстрации, см. Код distance функция.
Да, Дейкстра и BFS дадут вам ответ, но я думаю, что шахматный контекст этой проблемы дает знания, которые могут дать решение, которое намного быстрее, чем универсальный алгоритм кратчайшего пути, особенно на бесконечной шахматной доске.
Для простоты давайте опишем шахматную доску как плоскость (x, y). Цель состоит в том, чтобы найти кратчайший путь от (x0, y0) до (x1, y1), используя только возможные шаги (+-1, +-2), (+-2, +-1) и (+ -2), + -2), как описано в вопросе PS
Вот новое наблюдение: нарисуйте квадрат с углами (x-4,y-4), (x-4,y+4), (x+4,y-4), (x+4,y+4), Этот набор (назовите его S4) содержит 32 очка. Кратчайший путь от любой из этих 32 точек до (x, y) требует ровно двух ходов.
Кратчайший путь из любой из 24 точек в наборе S3 (определяется аналогично) до (x, y) требует как минимум двух ходов.
Следовательно, если |x1-x0|>4 или |y1-y0|>4, кратчайший путь из (x0, y0) в (x1, y1) ровно на два шага больше, чем кратчайший путь из (x0, y0) в S4. И последняя проблема может быть быстро решена с помощью простой итерации.
Пусть N = max(|x1-x0|,|y1-y0|). Если N>=4, то кратчайший путь от (x0, y0) до (x1, y1) имеет шаги ceil(N/2).
Ответ O(1) выше [ /questions/7768761/kratchajshij-put-ryitsarya-na-shahmatnoj-doske/7768789#7768789 от Mustafa Serdar Şanlı] на самом деле не работает. (Проверьте (1,1) или (3,2) или (4,4), за исключением очевидных краевых случаев (1,0) или (2,2)).
Ниже приведено гораздо более уродливое решение (python), которое работает (с добавленными "тестами"):
def solve(x,y):
x = abs(x)
y = abs(y)
if y > x:
temp=y
y=x
x=temp
if (x==2 and y==2):
return 4
if (x==1 and y==0):
return 3
if(y == 0 or float(y) / float(x) <= 0.5):
xClass = x % 4
if (xClass == 0):
initX = x/2
elif(xClass == 1):
initX = 1 + (x/2)
elif(xClass == 2):
initX = 1 + (x/2)
else:
initX = 1 + ((x+1)/2)
if (xClass > 1):
return initX - (y%2)
else:
return initX + (y%2)
else:
diagonal = x - ((x-y)/2)
if((x-y)%2 == 0):
if (diagonal % 3 == 0):
return (diagonal/3)*2
if (diagonal % 3 == 1):
return ((diagonal/3)*2)+2
else:
return ((diagonal/3)*2)+2
else:
return ((diagonal/3)*2)+1
def test():
real=[
[0,3,2,3,2,3,4,5,4,5,6,7,6,7],
[3,2,1,2,3,4,3,4,5,6,5,6,7,8],
[2,1,4,3,2,3,4,5,4,5,6,7,6,7],
[3,2,3,2,3,4,3,4,5,6,5,6,7,8],
[2,3,2,3,4,3,4,5,4,5,6,7,6,7],
[3,4,3,4,3,4,5,4,5,6,5,6,7,8],
[4,3,4,3,4,5,4,5,6,5,6,7,6,7],
[5,4,5,4,5,4,5,6,5,6,7,6,7,8],
[4,5,4,5,4,5,6,5,6,7,6,7,8,7],
[5,6,5,6,5,6,5,6,7,6,7,8,7,8],
[6,5,6,5,6,5,6,7,6,7,8,7,8,9],
[7,6,7,6,7,6,7,6,7,8,7,8,9,8]]
for x in range(12):
for y in range(12):
res = solve(x,y)
if res!= real[x][y]:
print (x, y), "failed, and returned", res, "rather than", real[x][y]
else:
print (x, y), "worked. Cool!"
test()
Что вам нужно сделать, так это думать о возможных ходах коня как о графике, где каждая позиция на доске - это узел, а возможные перемещения - в другую позицию как ребро. Нет необходимости в алгоритме Дейкстры, потому что каждое ребро имеет одинаковый вес или расстояние (все они такие же простые или короткие). Вы можете просто выполнить поиск BFS от начальной точки, пока не достигнете конечной позиции.
Решение из первых принципов в Python
Впервые я столкнулся с этой проблемой в тесте Codility. Мне дали 30 минут, чтобы решить эту проблему - мне потребовалось гораздо больше времени, чтобы достичь этого результата! Проблема заключалась в следующем: сколько ходов требуется рыцарю, чтобы перейти от 0,0 до x,y, используя только легальные ходы Рыцаря. x и y были более или менее неограничены (поэтому мы не говорим здесь о простой шахматной доске 8x8).
Они хотели O(1) решение. Я хотел найти решение, в котором программа явно решала проблему (т.е. я хотел что-то более очевидно правильное, чем паттерн Грэма - паттерны имеют привычку ломаться там, где вы не смотрите), и я действительно хотел не полагаться на бесспорная формула, как в решении Мустафы
Итак, вот мое решение, для чего оно стоит. Начните, как и другие, отметив, что решение симметрично относительно осей и диагоналей, поэтому нам нужно решать только для 0 >= y >= x. Для простоты объяснения (и кода) я собираюсь обратить проблему вспять: рыцарь начинает с x,y и стремится к 0,0.
Давайте предположим, что мы сократили проблему до уровня источника. Мы вернемся к тому, что на самом деле означает "vicinty", но сейчас давайте просто напишем некоторые решения в виде таблицы (источник слева внизу):
2 1 4 3
3 2 1 2
0 3 2 3
Таким образом, учитывая x,y на сетке, мы можем просто считать количество ходов в начало координат.
Если мы начали вне сетки, мы должны вернуться к ней. Мы вводим "среднюю линию", которая является линией, представленной y=x/2. Любой рыцарь в точке x,y на этой линии может вернуться к шпаргалке, используя серию 8-часовых ходов (то есть: (-2,-1) ходов). Если x,y лежит выше средней линии, то нам понадобится последовательность ходов в 8 часов и 7 часов, а если она находится ниже средней линии, нам понадобится последовательность в 8 часов и 10 часов. Часы движутся. Здесь нужно отметить две вещи:
- Эти последовательности являются, вероятно, кратчайшими путями. (Хотите, чтобы я это доказал, или это очевидно?)
- Мы заботимся только о количестве таких ходов. Мы можем смешивать и сочетать ходы в любом порядке.
Итак, давайте посмотрим на выше среднего движения. Мы утверждаем, что:
(dx;dy) = (2,1; 1,2) (n8; n7) (матричная запись, без набора математических символов - вектор столбца (dx;dy) равен квадратной матрице, умноженной на вектор столбца (n8;n7) - число ходов в 8 часов и количество ходов в 7 часов) и аналогично;
(dx;dy) = (2,2; 1, -1) (n8; n10)
Я утверждаю, что dx,dy будет примерно (x,y), поэтому (x-dx, y-dy) будет в окрестности источника (какой бы "окрестностью" не оказался).
Две строки в коде, которые вычисляют эти термины, являются решением для них, но они выбраны, чтобы иметь некоторые полезные свойства:
- Формула выше средней линии перемещает (x,y) к одному из (0,0), (1,1) или (2,2).
- Формула ниже средней линии перемещается (x,y) к одному из (0,0), (1,0), (2,0) или (1,1).
(Вы хотите доказательства этого?) Итак, расстояние Рыцаря будет суммой n7, n8, n10 и шпаргалки [x-dx, y-dy], и наша шпаргалка сводится к следующему:
. . 4
. 2 .
0 3 2
Теперь, это не совсем конец истории. Посмотрите на 3 в нижнем ряду. Единственные способы, которыми мы можем достичь этого:
- Мы начали там, или
- Мы переехали туда на 8 и 10 часов. Но если последний ход был 8 часов (что он имеет право, так как мы можем делать наши ходы в любом порядке), то мы должны были пройти через (3,1), расстояние которого на самом деле 2 (как вы можете см. из оригинальной таблицы). Итак, что мы должны сделать - это вернуться на 8 часов назад, сохранив всего два хода.
Аналогичная оптимизация будет с 4 справа вверху. Помимо начала, единственный способ достичь этого - это 8-часовой ход из (4,3). Этого нет в шпаргалке, но если бы он был там, его расстояние было бы 3, потому что вместо этого мы могли бы иметь 7 occlocked to (3,1), который имеет расстояние только 2. Таким образом, мы должны вернуться на один Двигайтесь на 8 часов, а затем идите вперед на 7 часов.
Итак, нам нужно добавить еще один номер в чит-лист:
. . 4
. 2 . 2
0 3 2
(Примечание: существует целый ряд оптимизаций обратного отслеживания из (0,1) и (0,2), но, поскольку решатель никогда не приведет нас туда, нам не нужно беспокоиться о них.)
Итак, вот код Python для оценки этого:
def knightDistance (x, y):
# normalise the coordinates
x, y = abs(x), abs(y)
if (x<y): x, y = y, x
# now 0 <= y <= x
# n8 means (-2,-1) (8 o'clock), n7 means (-1,-2) (7 o'clock), n10 means (-2,+1) (10 o'clock)
if (x>2*y):
# we're below the midline. Using 8- & 10-o'clock moves
n7, n8, n10 = 0, (x + 2*y)//4, (x - 2*y + 1)//4
else:
# we're above the midline. Using 7- and 8-o'clock moves
n7, n8, n10 = (2*y - x)//3, (2*x - y)//3, 0
x -= 2*n8 + n7 + 2*n10
y -= n8 + 2*n7 - n10
# now 0<=x<=2, and y <= x. Also (x,y) != (2,1)
# Try to optimise the paths.
if (x, y)==(1, 0): # hit the 3. Did we need to?
if (n8>0): # could have passed through the 2 at 3,1. Back-up
x, y = 3, 1; n8-=1;
if (x, y)==(2, 2): # hit the 4. Did we need to?
if (n8>0): # could have passed through a 3 at 4,3. Back-up, and take 7 o'clock to 2 at 3,1
x, y = 3, 1; n8-=1; n7+=1
# Almost there. Now look up the final leg
cheatsheet = [[0, 3, 2], [2, None, 2], [4]]
return n7 + n8 + n10 + cheatsheet [y][x-y]
Кстати, если вы хотите узнать фактический маршрут, то этот алгоритм также обеспечивает это: это просто последовательность n7 7-часовых ходов, за которыми следуют (или чередуются) n8 8-часовых ходов, n10 10- Часы движутся, и любой танец диктуется шпаргалкой (которая сама по себе может быть в шпаргалке).
Теперь: как доказать это правильно. Недостаточно просто сравнить эти результаты с таблицей правильных ответов, потому что сама проблема не ограничена. Но мы можем сказать, что если расстояние Рыцаря от квадрата s равно d, то, если {m} - множество допустимых шагов от s, расстояние Рыцаря (s+m) должно быть либо d-1, либо d+1. для всех м. (Вам нужно доказательство этого?) Кроме того, должен быть хотя бы один такой квадрат, расстояние которого равно d-1, если s не является источником. Таким образом, мы можем доказать правильность, показывая, что это свойство выполняется для каждого квадрата. Таким образом:
def validate (n):
def isSquareReasonable (x, y):
d, downhills = knightDistance (x, y), 0
moves = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
for dx, dy in moves:
dd = knightDistance (x+dx, y+dy)
if (dd == d+1): pass
elif (dd== d-1): downhills += 1
else: return False;
return (downhills>0) or (d==0)
for x in range (0, n+1):
for y in range (0, n+1):
if not isSquareReasonable (x, y): raise RuntimeError ("Validation failed")
В качестве альтернативы, мы можем доказать правильность любого квадрата s, преследуя маршрут от s под гору до начала координат. Сначала проверьте s на разумность, как указано выше, затем выберите любой s + m, такой что расстояние (s+m) == d-1. Повторяйте, пока мы не достигнем начала координат.
Howzat?
Я думаю, что это также может помочь вам..
NumWays(x,y)=1+min(NumWays(x+-2,y-+1),NumWays(x+-1,y+-2));
и используя динамическое программирование, чтобы получить решение.
PS: он как бы использует BFS без необходимости объявлять узлы и ребра графа.
/*
This program takes two sets of cordinates on a 8*8 chessboard, representing the
starting and ending points of a knight's path.
The problem is to print the cordinates that the knight traverses in between, following
the shortest path it can take.
Normally this program is to be implemented using the Djikstra's algorithm(using graphs)
but can also be implemented using the array method.
NOTE:Between 2 points there may be more than one shortest path. This program prints
only one of them.
*/
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
int m1=0,m2=0;
/*
This array contains three columns and 37 rows:
The rows signify the possible coordinate differences.
The columns 1 and 2 contains the possible permutations of the row and column difference
between two positions on a chess board;
The column 3 contains the minimum number of steps involved in traversing the knight's
path with the given permutation*/
int arr[37][3]={{0,0,0},{0,1,3},{0,2,2},{0,3,3},{0,4,2},{0,5,3},{0,6,4},{0,7,5}, {1,1,2},{1,2,1},{1,3,2},{1,4,3},{1,5,4},{1,6,3},{1,7,4},{2,2,4},{2,3,3},{2,4,2},
{2,5,3},{2,6,3},{2,7,5},{3,3,2},{3,4,3},{3,5,4},{3,6,3},{3,7,4},{4,4,4},{4,5,3},{4,6,4},{4,7,5},{5,5,4},{5,6,5},{5,7,4},{6,6,5},{6,7,5},{7,7,6}};
void printMoves(int,int,int,int,int,int);
void futrLegalMove(int,int,int,int);
main()
{
printf("KNIGHT'S SHORTEST PATH ON A 8*8 CHESSBOARD :\n");
printf("------------------------------------------");
printf("\nThe chessboard may be treated as a 8*8 array here i.e. the (1,1) ");
printf("\non chessboard is to be referred as (0,0) here and same for (8,8) ");
printf("\nwhich is to be referred as (7,7) and likewise.\n");
int ix,iy,fx,fy;
printf("\nEnter the initial position of the knight :\n");
scanf("%d%d",&ix,&iy);
printf("\nEnter the final position to be reached :\n");
scanf("%d%d",&fx,&fy);
int px=ix,py=iy;
int temp;
int tx,ty;
printf("\nThe Knight's shortest path is given by :\n\n");
printf("(%d, %d)",ix,iy);
futrLegalMove(px,py,m1,m2);
printMoves(px,py,fx,fy,m1,m2);
getch();
}
/*
This method checkSteps() checks the minimum number of steps involved from current
position(a & b) to final position(c & d) by looking up in the array arr[][].
*/
int checkSteps(int a,int b,int c,int d)
{
int xdiff, ydiff;
int i, j;
if(c>a)
xdiff=c-a;
else
xdiff=a-c;
if(d>b)
ydiff=d-b;
else
ydiff=b-d;
for(i=0;i<37;i++)
{
if(((xdiff==arr[i][0])&&(ydiff==arr[i][1])) || ((xdiff==arr[i][1])&& (ydiff==arr[i] [0])))
{
j=arr[i][2];break;
}
}
return j;
}
/*
This method printMoves() prints all the moves involved.
*/
void printMoves(int px,int py, int fx, int fy,int a,int b)
{
int temp;
int tx,ty;
int t1,t2;
while(!((px==fx) && (py==fy)))
{
printf(" --> ");
temp=checkSteps(px+a,py+b,fx,fy);
tx=px+a;
ty=py+b;
if(!(a==2 && b==1))
{if((checkSteps(px+2,py+1,fx,fy)<temp) && checkMove(px+2,py+1))
{temp=checkSteps(px+2,py+1,fx,fy);
tx=px+2;ty=py+1;}}
if(!(a==2 && b==-1))
{if((checkSteps(px+2,py-1,fx,fy)<temp) && checkMove(px+2,py-1))
{temp=checkSteps(px+2,py-1,fx,fy);
tx=px+2;ty=py-1;}}
if(!(a==-2 && b==1))
{if((checkSteps(px-2,py+1,fx,fy)<temp) && checkMove(px-2,py+1))
{temp=checkSteps(px-2,py+1,fx,fy);
tx=px-2;ty=py+1;}}
if(!(a==-2 && b==-1))
{if((checkSteps(px-2,py-1,fx,fy)<temp) && checkMove(px-2,py-1))
{temp=checkSteps(px-2,py-1,fx,fy);
tx=px-2;ty=py-1;}}
if(!(a==1 && b==2))
{if((checkSteps(px+1,py+2,fx,fy)<temp) && checkMove(px+1,py+2))
{temp=checkSteps(px+1,py+2,fx,fy);
tx=px+1;ty=py+2;}}
if(!(a==1 && b==-2))
{if((checkSteps(px+1,py-2,fx,fy)<temp) && checkMove(px+1,py-2))
{temp=checkSteps(px+1,py-2,fx,fy);
tx=px+1;ty=py-2;}}
if(!(a==-1 && b==2))
{if((checkSteps(px-1,py+2,fx,fy)<temp) && checkMove(px-1,py+2))
{temp=checkSteps(px-1,py+2,fx,fy);
tx=px-1;ty=py+2;}}
if(!(a==-1 && b==-2))
{if((checkSteps(px-1,py-2,fx,fy)<temp) && checkMove(px-1,py-2))
{temp=checkSteps(px-1,py-2,fx,fy);
tx=px-1;ty=py-2;}}
t1=tx-px;//the step taken in the current move in the x direction.
t2=ty-py;//" " " " " " " " " " " " " " " " " " " " " y " " " " ".
px=tx;
py=ty;
printf("(%d, %d)",px,py);
futrLegalMove(px,py,t1,t2);
a=m1;
b=m2;
}
}
/*
The method checkMove() checks whether the move in consideration is beyond the scope of
board or not.
*/
int checkMove(int a, int b)
{
if(a>7 || b>7 || a<0 || b<0)
return 0;
else
return 1;
}
/*Out of the 8 possible moves, this function futrLegalMove() sets the valid move by
applying the following constraints
1. The next move should not be beyond the scope of the board.
2. The next move should not be the exact opposite of the previous move.
The 1st constraint is checked by sending all possible moves to the checkMove()
method;
The 2nd constraint is checked by passing as parameters(i.e. a and b) the steps of the
previous move and checking whether or not it is the exact opposite of the current move.
*/
void futrLegalMove(int px,int py,int a,int b)
{
if(checkMove(px+2,py+1) && (a!=-2 && b!=-1))
m1=2,m2=1;
else
{
if(checkMove(px+2,py-1)&& (a!=-2 && b!=1))
m1=2,m2=-1;
else
{
if(checkMove(px-2,py+1)&& (a!=2 && b!=-1))
m1=-2,m2=1;
else
{
if(checkMove(px-2,py-1)&& (a!=2 && b!=1))
m1=-2,m2=-1;
else
{
if(checkMove(px+1,py+2)&& (b!=-2 && a!=-1))
m2=2,m1=1;
else
{
if(checkMove(px+1,py-2)&& (a!=-1 && b!=2))
m2=-2,m1=1;
else
{
if(checkMove(px-1,py+2)&& (a!=1 && b!=-2))
m2=2,m1=-1;
else
{
if(checkMove(px-1,py-2)&& (a!=1 && b!=2))
m2=-2,m1=-1;
}}}}}}}
}
//End of Program.
Я еще не изучал графики. Что касается проблемы реализации с помощью простых массивов, я не мог найти никакого другого решения, кроме этого. Я рассматривал позиции не как ранги и файлы (обычные шахматные обозначения), а как индексы массивов. К вашему сведению, это только для шахматной доски 8*8. Любые советы по улучшению всегда приветствуются.
* Комментарии должны быть достаточными для вашего понимания логики. Тем не менее, вы всегда можете спросить.
* Проверено на компиляторе DEV-C++ 4.9.9.2 (Bloodshed Software).
Вот решение этой конкретной проблемы, реализованное в Perl. Он покажет один из самых коротких путей - в некоторых случаях их может быть несколько.
Я не использовал ни один из описанных выше алгоритмов, но было бы неплохо сравнить его с другими решениями.
#!/usr/local/bin/perl -w
use strict;
my $from = [0,0];
my $to = [7,7];
my $f_from = flat($from);
my $f_to = flat($to);
my $max_x = 7;
my $max_y = 7;
my @moves = ([-1,2],[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1]);
my %squares = ();
my $i = 0;
my $min = -1;
my @s = ( $from );
while ( @s ) {
my @n = ();
$i++;
foreach my $s ( @s ) {
unless ( $squares{ flat($s) } ) {
my @m = moves( $s );
push @n, @m;
$squares{ flat($s) } = { i=>$i, n=>{ map {flat($_)=>1} @m }, };
$min = $i if $squares{ flat($s) }->{n}->{$f_to};
}
}
last if $min > -1;
@s = @n;
}
show_path( $f_to, $min );
sub show_path {
my ($s,$i) = @_;
return if $s eq $f_from;
print "$i => $f_to\n" if $i == $min;
foreach my $k ( keys %squares ) {
if ( $squares{$k}->{i} == $i && $squares{$k}->{n}->{$s} ) {
$i--;
print "$i => $k\n";
show_path( $k, $i );
last;
}
}
}
sub flat { "$_[0]->[0],$_[0]->[1]" }
sub moves {
my $c = shift;
my @s = ();
foreach my $m ( @moves ) {
my $x = $c->[0] + $m->[0];
my $y = $c->[1] + $m->[1];
if ( $x >= 0 && $x <=$max_x && $y >=0 && $y <=$max_y) {
push @s, [$x, $y];
}
}
return @s;
}
__END__
public class Horse {
private int[][] board;
private int[] xer = { 2, 1, -1, -2, -2, -1, 1, 2 };
private int[] yer = { 1, 2, 2, 1, -1, -2, -2, -1 };
private final static int A_BIG_NUMBER = 10000;
private final static int UPPER_BOUND = 64;
public Horse() {
board = new int[8][8];
}
private int solution(int x, int y, int destx, int desty, int move) {
if(move == UPPER_BOUND) {
/* lets put an upper bound to avoid stack overflow */
return A_BIG_NUMBER;
}
if(x == 6 && y ==5) {
board[6][5] = 1;
return 1;
}
int min = A_BIG_NUMBER;
for (int i = 0 ; i < xer.length; i++) {
if (isMoveGood(x + xer[i], y + yer[i])) {
if(board[x + xer[i]][y + yer[i]] != 0) {
min = Integer.min(min, 1 + board[x +xer[i]] [y +yer[i]]);
} else {
min = Integer.min(min, 1 + solution(x + xer[i], y + yer[i], destx, desty, move + 1));
}
}
}
board[x][y] = min;
return min;
}
private boolean isMoveGood(int x, int y) {
if (x >= 0 && x < board.length && y >= 0 && y < board.length)
return true;
return false;
}
public static void main(String[] args) {
int destX = 6;
int destY = 7;
final Horse h = new Horse();
System.out.println(h.solution(0, 0, destX, destY, 0));
}
}
Вот моя программа. Это не идеальное решение. В рекурсивную функцию нужно внести много изменений. Но этот конечный результат идеален. Я попытался немного оптимизировать.
public class KnightKing2 {
private static int tempCount = 0;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int ip1 = Integer.parseInt(in.nextLine().trim());
int ip2 = Integer.parseInt(in.nextLine().trim());
int ip3 = Integer.parseInt(in.nextLine().trim());
int ip4 = Integer.parseInt(in.nextLine().trim());
in.close();
int output = getStepCount(ip1, ip2, ip3, ip4);
System.out.println("Shortest Path :" + tempCount);
}
// 2 1 6 5 -> 4
// 6 6 5 5 -> 2
public static int getStepCount(int input1, int input2, int input3, int input4) {
return recurse(0, input1, input2, input3, input4);
}
private static int recurse(int count, int tx, int ty, int kx, int ky) {
if (isSolved(tx, ty, kx, ky)) {
int ccount = count+1;
System.out.println("COUNT: "+count+"--"+tx+","+ty+","+ccount);
if((tempCount==0) || (ccount<=tempCount)){
tempCount = ccount;
}
return ccount;
}
if ((tempCount==0 || count < tempCount) && ((tx < kx+2) && (ty < ky+2))) {
if (!(tx + 2 > 8) && !(ty + 1 > 8)) {
rightTop(count, tx, ty, kx, ky);
}
if (!(tx + 2 > 8) && !(ty - 1 < 0)) {
rightBottom(count, tx, ty, kx, ky);
}
if (!(tx + 1 > 8) && !(ty + 2 > 8)) {
topRight(count, tx, ty, kx, ky);
}
if (!(tx - 1 < 0) && !(ty + 2 > 8)) {
topLeft(count, tx, ty, kx, ky);
}
if (!(tx + 1 > 8) && !(ty - 2 < 0)) {
bottomRight(count, tx, ty, kx, ky);
}
if (!(tx - 1 < 0) && !(ty - 2 < 0)) {
bottomLeft(count, tx, ty, kx, ky);
}
if (!(tx - 2 < 0) && !(ty + 1 > 8)) {
leftTop(count, tx, ty, kx, ky);
}
if (!(tx - 2 < 0) && !(ty - 1 < 0)) {
leftBottom(count, tx, ty, kx, ky);
}
}
return count;
}
private static int rightTop(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx + 2, ty + 1, kx, ky);
}
private static int topRight(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx + 1, ty + 2, kx, ky);
}
private static int rightBottom(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx + 2, ty - 1, kx, ky);
}
private static int bottomRight(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx + 1, ty - 2, kx, ky);
}
private static int topLeft(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx - 1, ty + 2, kx, ky);
}
private static int bottomLeft(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx - 1, ty - 2, kx, ky);
}
private static int leftTop(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx - 2, ty + 1, kx, ky);
}
private static int leftBottom(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx - 2, ty - 1, kx, ky);
}
private static boolean isSolved(int tx, int ty, int kx, int ky) {
boolean solved = false;
if ((tx == kx) && (ty == ky)) {
solved = true;
} else if ((tx + 2 == kx) && (ty + 1 == ky)) { // right top
solved = true;
} else if ((tx + 2 == kx) && (ty - 1 == ky)) { // right bottom
solved = true;
} else if ((ty + 2 == ky) && (tx + 1 == kx)) {// top right
solved = true;
} else if ((ty + 2 == ky) && (tx - 1 == kx)) {// top left
solved = true;
} else if ((tx - 2 == kx) && (ty + 1 == ky)) { // left top
solved = true;
} else if ((tx - 2 == kx) && (ty - 1 == ky)) {// left bottom
solved = true;
} else if ((ty - 2 == ky) && (tx + 1 == kx)) { // bottom right
solved = true;
} else if ((ty - 2 == ky) && (tx - 1 == kx)) { // bottom left
solved = true;
}
return solved;
}
}
Я думал, что предоставлю интуитивное жадное решение (O(max(горизонтальное расстояние, вертикальное расстояние))), которое легче понять, чем решение с постоянным временем, но намного быстрее, чем алгоритм поиска. Это в контексте бесконечной шахматной доски.
Суть этого решения заключается в изучении геометрии и понимании того, что для всех случаев, когда конь уходит больше двух, вы можете просто выбрать путь, который приближает вас к конечной точке.
- Пока вы отошли более чем на два хода коня, двигайтесь в направлении (x, y), сделав 2 шага в направлении той координаты, которая находится дальше, и 1 шаг в направлении той координаты, которая ближе.
- Как только вы окажетесь в пределах двух ходов коня, обратитесь к справочной таблице.
int minKnightMoves(int x, int y) {
vector<vector<int>> table = {{4, 3, 2, 3, 2, 3, 2, 3, 4},
{3, 2, 3, 2, 3, 2, 3, 2, 3},
{2, 3, 4, 1, 2, 1, 4, 3, 2},
{3, 2, 1, 2, 3, 2, 1, 2, 3},
{2, 3, 2, 3, 0, 3, 2, 3, 2},
{3, 2, 1, 2, 3, 2, 1, 2, 3},
{2, 3, 4, 1, 2, 1, 4, 3, 2},
{3, 2, 3, 2, 3, 2, 3, 2, 3},
{4, 3, 2, 3, 2, 3, 2, 3, 4}};
int x0 = 0, y0 = 0, x1 = x, y1 = y;
int x_dist = x1, y_dist = y1, max_dist = table.size() / 2, moves = 0;
while (abs(x_dist) > max_dist || abs(y_dist) > max_dist) {
if (abs(x_dist) > abs(y_dist)) {
x0 += (x_dist > 0) ? 2 : -2;
y0 += (y_dist > 0) ? 1 : -1;
} else {
x0 += (x_dist > 0) ? 1 : -1;
y0 += (y_dist > 0) ? 2 : -2;
}
x_dist = x1 - x0, y_dist = y1 - y0;
moves++;
}
return moves + table[x_dist + 4][y_dist + 4];
}
Вот PHP-версия функции Жюля Мэй
function knightDistance($x, $y)
{
$x = abs($x);
$y = abs($y);
if($x < $y)
{
$tmp = $x;
$x = $y;
$y = $tmp;
}
if($x > 2 * $y)
{
$n7 = 0;
$n8 = floor(($x + 2*$y) / 4);
$n10 = floor(($x - 2*$y +1) / 4);
}
else
{
$n7 = floor((2*$y - $x) / 3);
$n8 = floor((2*$x - $y) / 3);
$n10 = 0;
}
$x -= 2 * $n8 + $n7 + 2 * $n10;
$y -= $n8 + 2 * $n7 - $n10;
if($x == 1 && $y == 0)
{
if($n8 > 0)
{
$x = 3;
$y = 1;
$n8--;
}
}
if($x == 2 && $y == 2)
{
if($n8 > 0)
{
$x = 3;
$y = 1;
$n8--;
$n7++;
}
}
$cheatsheet = [[0, 3, 2], [2, 0, 2], [4]];
return $n7 + $n8 + $n10 + $cheatsheet [$y][$x-$y];
}
Кажется, работает только код ruby из jsfiddle ответа Грэма Пайла выше, чередующий весь дополнительный код и преобразующий оставшийся в ruby только для того, чтобы получить решение по его алгоритму. Тем не менее, тестирование:
def getBoardOffset(board)
return board.length / 2
end
def setMoveCount(x, y, count, board)
offset = getBoardOffset(board)
board[y + offset][x + offset] = count
end
def getMoveCount(x, y, board)
offset = getBoardOffset(board)
row = board[y + offset]
return row[x + offset]
end
def isBottomOfVerticalCase(x, y)
return (y - 2 * x) % 4 == 0
end
def isPrimaryDiagonalCase(x, y)
return (x + y) % 2 == 0
end
def isSecondaryDiagonalCase(x, y)
return (x + y) % 2 == 1
end
def simplifyBySymmetry(x, y)
x = x.abs
y = y.abs
if (y < x)
t = x
x = y
y = t
end
return {x: x, y: y}
end
def getPrimaryDiagonalCaseMoveCount(x, y)
var diagonalOffset = y + x
var diagonalIntersect = diagonalOffset / 2
return ((diagonalIntersect + 2) / 3).floor * 2
end
def getSpecialCaseMoveCount(x, y)
specials = [{
x: 0,
y: 0,
d: 0
},
{
x: 0,
y: 1,
d: 3
},
{
x: 0,
y: 2,
d: 2
},
{
x: 0,
y: 3,
d: 3
},
{
x: 2,
y: 2,
d: 4
},
{
x: 1,
y: 1,
d: 2
},
{
x: 3,
y: 3,
d: 2
}
];
matchingSpecial=nil
specials.each do |special|
if (special[:x] == x && special[:y] == y)
matchingSpecial = special
end
end
if (matchingSpecial)
return matchingSpecial[:d]
end
end
def isVerticalCase(x, y)
return y >= 2 * x
end
def getVerticalCaseMoveCount(x, y)
normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y)
groupIndex = (normalizedHeight/4).floor
groupStartMoveCount = groupIndex * 2 + x
return groupStartMoveCount + getIndexInVerticalGroup(x, y)
end
def getIndexInVerticalGroup(x, y)
return getNormalizedHeightForVerticalGroupCase(x, y) % 4
end
def getYOffsetForVerticalGroupCase(x)
return x * 2
end
def getNormalizedHeightForVerticalGroupCase(x, y)
return y - getYOffsetForVerticalGroupCase(x)
end
def getSecondaryDiagonalCaseMoveCount(x, y)
diagonalOffset = y + x
diagonalIntersect = diagonalOffset / 2 - 1
return ((diagonalIntersect + 2) / 3).floor * 2 + 1
end
def getMoveCountO1(x, y)
newXY = simplifyBySymmetry(x, y)
x = newXY[:x]
y = newXY[:y]
specialMoveCount = getSpecialCaseMoveCount(x ,y)
if (specialMoveCount != nil)
return specialMoveCount
elsif (isVerticalCase(x, y))
return getVerticalCaseMoveCount(x ,y)
elsif (isPrimaryDiagonalCase(x, y))
return getPrimaryDiagonalCaseMoveCount(x ,y)
elsif (isSecondaryDiagonalCase(x, y))
return getSecondaryDiagonalCaseMoveCount(x ,y)
end
end
def solution(x ,y)
return getMoveCountO1(x, y)
end
puts solution(0,0)
Единственное намерение - сэкономить время на преобразование кода, если кому-то нужен полный код.
Я хотел бы внести свой вклад в этот вопрос с моей версией в Javascript. Мой алгоритм находит набор кратчайших путей к цели.
Ваше здоровье!
static size = 8;
targetPos = [];
targetToken = 't';
moveToken = 'a';
static isOutOfBoundaries(x,y){
if(x>Board.size-1||x<0)
return true;
else if(y>Board.size-1||y<0)
return true;
else
return false;
}
constructor(){
this.tiles = Array.from(Array(Board.size), ()=>Array.from(Array(Board.size), tile=>'·'));
}
visualize(){
this.tiles.forEach(row=>console.log(row.join(' ')));
}
placeItem(position, token){
if(Board.isOutOfBoundaries(position[0],position[1]))
throw new Error(`Piece/Target is out board boundaries`);
else
this.tiles[position[1]][position[0]] = token;
}
markPieceMoves(piece){
for(let i = 0; i<piece.moves.length; ++i)
this.tiles[piece.moves[i][1]][piece.moves[i][0]] = this.moveToken;
}
}
class MovesTree{
constructor(position){
this.pos = position;
// -
//|
//|
this.uur = null;
// |
//--
this.rru = null;
//--
// |
this.rrd = null;
//|
//|
// -
this.ddr = null;
// |
// |
//-
this.ddl = null;
// --
//|
this.lld = null;
//|
// --
this.llu = null;
//-
// |
// |
this.uul = null;
}
static getMoves(node){
const twoSteps = 2;
const oneStep = 1;
// -
//|
//|
if(!Board.isOutOfBoundaries(node.pos[0]+oneStep,node.pos[1]-twoSteps))
node.uur=new MovesTree([node.pos[0]+oneStep,node.pos[1]-twoSteps]);
// |
//--
if(!Board.isOutOfBoundaries(node.pos[0]+twoSteps,node.pos[1]-oneStep))
node.rru=new MovesTree([node.pos[0]+twoSteps,node.pos[1]-oneStep]);
//--
// |
if(!Board.isOutOfBoundaries(node.pos[0]+twoSteps,node.pos[1]+oneStep))
node.rrd=new MovesTree([node.pos[0]+twoSteps,node.pos[1]+oneStep]);
//|
//|
// -
if(!Board.isOutOfBoundaries(node.pos[0]+oneStep,node.pos[1]+twoSteps))
node.ddr=new MovesTree([node.pos[0]+oneStep,node.pos[1]+twoSteps]);
// |
// |
//-
if(!Board.isOutOfBoundaries(node.pos[0]-oneStep,node.pos[1]+twoSteps))
node.ddl=new MovesTree([node.pos[0]-oneStep,node.pos[1]+twoSteps]);
// --
//|
if(!Board.isOutOfBoundaries(node.pos[0]-twoSteps,node.pos[1]+oneStep))
node.lld=new MovesTree([node.pos[0]-twoSteps,node.pos[1]+oneStep]);
//|
// --
if(!Board.isOutOfBoundaries(node.pos[0]-twoSteps,node.pos[1]-oneStep))
node.llu=new MovesTree([node.pos[0]-twoSteps,node.pos[1]-oneStep]);
//-
// |
// |
if(!Board.isOutOfBoundaries(node.pos[0]-oneStep,node.pos[1]-twoSteps))
node.uul=new MovesTree([node.pos[0]-oneStep,node.pos[1]-twoSteps]);
}
BFS(func,target){
let queue = [this];
while(queue.length>0){
if(target.toString()!==queue[0].pos.toString()){
MovesTree.getMoves(queue[0])
queue.push(...func(queue[0]));
}
else
return;
queue.shift();
}
}
DFS(node, target, path){
let visited;
path === undefined ? visited = [node.pos]: visited = this.mergePath(path, node.pos);
if(node.pos.toString()===target.toString()){
visited.reverse();
console.log(visited);
return;
}
else{
if(node.uur!==null)
this.DFS(node.uur, target, visited);
if(node.rru!==null)
this.DFS(node.rru, target, visited);
if(node.rrd!==null)
this.DFS(node.rrd, target, visited);
if(node.ddr!==null)
this.DFS(node.ddr, target, visited);
if(node.ddl!==null)
this.DFS(node.ddl, target, visited);
if(node.lld!==null)
this.DFS(node.lld, target, visited);
if(node.llu!==null)
this.DFS(node.llu, target, visited);
if(node.uul!==null)
this.DFS(node.uul, target, visited);
}
}
toArray(node){
let array = [];
if(node.uur!==null)
array.push(node.uur);
if(node.rru!==null)
array.push(node.rru);
if(node.rrd!==null)
array.push(node.rrd);
if(node.ddr!==null)
array.push(node.ddr);
if(node.ddl!==null)
array.push(node.ddl);
if(node.lld!==null)
array.push(node.lld);
if(node.llu!==null)
array.push(node.llu);
if(node.uul!==null)
array.push(node.uul);
return array;
}
mergePath(path, current){
let merged = [];
merged.push(current);
path.forEach(step=>{
merged.push(step)
});
return merged;
}
}
class Knight{
token = 'k';
constructor(row,col){
this.position = [row,col];
this.moves = new MovesTree(this.position,this);
}
}
const board = new Board();
board.targetPos = [6,0];
const knight = new Knight(0,7);
board.placeItem(knight.position, knight.token);
board.placeItem(board.targetPos, board.targetToken)
knight.moves.BFS(knight.moves.toArray, board.targetPos);
knight.moves.DFS(knight.moves, board.targetPos)
board.visualize();
Вот еще одно рабочее решение Python (от Johan du Toit):
Вход:
1<=sx,sy,tx,ty<=8
def knightDistance( sx, sy, tx, ty):
def test(x1, y1, x2, y2):
return (sx == x1 and sy == y1 and tx == x2 and ty == y2) or (sx == x2 and sy == y2 and tx == x1 and ty==y1)
# special corner cases
if (test(1, 1, 2, 2) or
test(7, 7, 8, 8) or
test(7, 2, 8, 1) or
test(1, 8, 2, 7)):
return 4
# axes symmetry
x = abs(sx - tx)
y = abs(sy - ty)
# diagonal symmetry
if (x < y):
x,y = y,x
# 2 corner cases
if (x == 1 and y == 0):
return 3
if (x == 2 and y == 2):
return 4
# main
delta = x - y;
if (y > delta) :
return int(delta - 2 * ((delta - y) // 3))
else:
return int(delta - 2 * ((delta - y) // 4))
Вот версия на C, основанная на коде Mustafa Serdar Şanlı, которая работает для конечной доски:
#include <stdio.h>
#include <math.h>
#define test(x1, y1, x2, y2) (sx == x1 && sy == y1 &&tx == x2 &&ty == y2) || (sx == x2 && sy == y2 && tx == x1 && ty==y1)
int distance(int sx, int sy, int tx, int ty) {
int x, y, t;
double delta;
// special corner cases
if (test(1, 1, 2, 2) ||
test(7, 7, 8, 8) ||
test(7, 2, 8, 1) ||
test(1, 8, 2, 7))
return 4;
// axes symmetry
x = abs(sx - tx);
y = abs(sy - ty);
// diagonal symmetry
if (x < y) {
t = x;
x = y;
y = t;
}
// 2 corner cases
if (x == 1 && y == 0)
return 3;
if (x == 2 && y == 2)
return 4;
// main
delta = x - y;
if (y > delta) {
return (int)(delta - 2 * floor((delta - y) / 3));
}
else {
return (int)(delta - 2 * floor((delta - y) / 4));
}
}
Проверьте это здесь с доказательством против рекурсивного решения