Кратчайший путь коня на шахматной доске
https://stackoverflow.com/questions/2339101
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я готовился к предстоящему соревнованию по программированию и наткнулся на вопрос, который меня совершенно сбил с толку.Тем не менее, я чувствую, что эту концепцию мне следует изучить сейчас, а не скрещивать пальцы, что она никогда не возникнет.
По сути, речь идет о фигуре коня на шахматной доске.Вам даны два входа:Начальное и конечное местоположение.Цель состоит в том, чтобы затем рассчитать и распечатать кратчайший путь, по которому рыцарь может добраться до целевой точки.
Я никогда не имел дела с вещами в стиле кратчайшего пути и даже не знаю, с чего начать.Какую логику я использую, чтобы решить эту проблему?
P.S.Если это имеет какое-то значение, они хотят, чтобы вы дополнили обычные ходы коня, позволив ему также ходить в четыре угла квадрата, образованного (потенциально) восемью ходами, которые конь может сделать, учитывая, что центр квадрата - это расположение рыцаря.
Решение
У вас есть график, где все доступные ходы связаны (значение = 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.Ну, я бы назвал это обманом, и работает только потому, что проблема маленькая.Но иногда соревнования будут проверять, как быстро работает ваша программа.
- Главное в том, что если вы готовитесь к конкурсу программирования, вы должны знать общие алгоритмы, включая Dijkstra's.Хорошая отправная точка — чтение
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 );
}
Примечание:Этот вопрос был задан на САКО 2007, день 1
И решения есть здесь
Вот правильное решение 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) дано на САКО 2007, день 1 решения.
Прежде всего я хочу оценить Грэм Пайл за очень красивую визуализацию, которая помогла мне исправить формулу.
По какой-то причине (может для упрощения или красоты или просто ошибка) перенесли 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), как описано в вопросе P.S.
Вот новое наблюдение:нарисуйте квадрат с углами (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) до С4.И последнюю проблему можно быстро решить с помощью простой итерации.
Пусть N = max(|x1-x0|,|y1-y0|).Если N>=4, то кратчайший путь от (x0,y0) до (x1,y1) имеет ячейка(N/2) шаги.
Ответ O(1) выше [https://stackoverflow.com/a/8778592/4288232 Мустафа Сердар Шанлы] на самом деле не работает.(Проверьте (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.
Давайте предположим, что мы сузили задачу до окрестности начала координат.Со временем мы доберемся до того, что на самом деле означает «близость», а пока давайте просто запишем некоторые решения в шпаргалку (начало внизу слева):
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;н10)
Я утверждаю, что 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 часов в (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.Повторяем, пока не достигнем начала координат.
Как?
/*
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).
Я думаю, что это тоже может вам помочь..
NumWays(x,y)=1+min(NumWays(x+-2,y-+1),NumWays(x+-1,y+-2));
и использование динамического программирования для получения решения.
P.S:Он как бы использует BFS без необходимости утруждать себя объявлением узлов и ребер графа.
Вот решение этой конкретной проблемы, реализованное в 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));
}
}
Просто рубиновый код из 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)
Единственное намерение — сэкономить кому-то время на преобразовании кода, если кому-то понадобится полный код.
вот 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];
}
Вот моя программа.Это не идеальное решение.В функцию рекурсии нужно внести множество изменений.Но этот конечный результат идеален.Я попробовал немного оптимизировать.
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;
}
}
Вот версия C, основанная на коде Мустафы Сердара Шанлы, которая работает для доски Finit:
#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));
}
}
Проверьте это здесь с доказательством против рекурсивного решения
