Минимальные шаги для достижения цели рыцарем | Комплект 2

Опубликовано: 16 Января, 2022

Учитывая квадратную шахматную доску размером N x N, позицию коня и позицию цели, задача состоит в том, чтобы определить минимальные шаги, которые предпримет конь, чтобы достичь целевой позиции.

Примеры :

Входные данные: (2, 4) - позиция коня, (6, 4) - целевая ячейка
Выход: 2

Ввод: (4, 5) (1, 1)
Выход: 3

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход BFS для решения вышеуказанной проблемы уже обсуждался в предыдущем посте. В этом посте обсуждается решение для динамического программирования.

Объяснение подхода:

  • Случай 1: Если цель не находится в одном ряду или одном столбце позиции коня.
    Пусть шахматная доска 8 х 8 клеток. Теперь предположим, что конь находится в (3, 3), а цель - в (7, 8). Возможны 8 ходов от текущей позиции коня, т.е. (2, 1), (1, 2), (4, 1), (1, 4), (5, 2), (2, 5), (5). , 4), (4, 5). Но из этих только два хода (5, 4) и (4, 5) будут направлены к цели, а все остальные - от цели. Итак, чтобы найти минимальные шаги, перейдите к (4, 5) или (5, 4). Теперь вычислите минимальные шаги, взятые из (4, 5) и (5, 4) для достижения цели. Это рассчитывается с помощью динамического программирования. Таким образом, это приводит к минимуму шагов от (3, 3) до (7, 8).
  • Случай 2: Если цель находится в одном ряду или одном столбце позиции коня.
    Пусть шахматная доска 8 х 8 клеток. Теперь предположим, что конь находится в (4, 3), а цель - в (4, 7). Возможно 8 ходов, но к цели всего 4 хода, то есть (5, 5), (3, 5), (2, 4), (6, 4). Поскольку, (5, 5) эквивалентно (3, 5), а (2, 4) эквивалентно (6, 4). Таким образом, из этих 4 баллов его можно преобразовать в 2 балла. Принимая (5, 5) и (6, 4) (здесь). Теперь рассчитайте минимальное количество шагов, сделанных из этих двух точек для достижения цели. Это рассчитывается с помощью динамического программирования. Таким образом, это приводит к минимуму шагов от (4, 3) до (4, 7).

Исключение: когда конь находится в углу, а цель такова, что разница координат x и y с положением коня составляет (1, 1) или наоборот. Тогда минимальное количество шагов будет 4.

Уравнение динамического программирования:

1) dp[diffOfX][diffOfY] is the minimum steps taken from knight’s position to target’s position.

2) dp[diffOfX][diffOfY] = dp[diffOfY][diffOfX].

where, diffOfX = difference between knight’s x-coordinate and target’s x-coordinate
diffOfY = difference between knight’s y-coordinate and target’s y-coordinate

Below is the implementation of above approach:

C++

// C++ code for minimum steps for
// a knight to reach target position
#include <bits/stdc++.h>
  
using namespace std;
  
// initializing the matrix.
int dp[8][8] = { 0 };
  
int getsteps(int x, int y, 
             int tx, int ty)
{
    // if knight is on the target 
    // position return 0.
    if (x == tx && y == ty)
        return dp[0][0];
    else {
          
        // if already calculated then return
        // that value. Taking absolute difference.
        if (dp[abs(x - tx)][abs(y - ty)] != 0)
            return dp[abs(x - tx)][abs(y - ty)];
              
        else {
  
            // there will be two distinct positions
            // from the knight towards a target.
            // if the target is in same row or column
            // as of knight than there can be four
            // positions towards the target but in that
            // two would be the same and the other two
            // would be the same.
            int x1, y1, x2, y2;
              
            // (x1, y1) and (x2, y2) are two positions.
            // these can be different according to situation.
            // From position of knight, the chess board can be
            // divided into four blocks i.e.. N-E, E-S, S-W, W-N .
            if (x <= tx) {
                if (y <= ty) {
                    x1 = x + 2;
                    y1 = y + 1;
                    x2 = x + 1;
                    y2 = y + 2;
                } else {
                    x1 = x + 2;
                    y1 = y - 1;
                    x2 = x + 1;
                    y2 = y - 2;
                }
            } else {
                if (y <= ty) {
                    x1 = x - 2;
                    y1 = y + 1;
                    x2 = x - 1;
                    y2 = y + 2;
                } else {
                    x1 = x - 2;
                    y1 = y - 1;
                    x2 = x - 1;
                    y2 = y - 2;
                }
            }
              
            // ans will be, 1 + minimum of steps 
            // required from (x1, y1) and (x2, y2).
            dp[abs(x - tx)][abs(y - ty)] = 
                           min(getsteps(x1, y1, tx, ty), 
                           getsteps(x2, y2, tx, ty)) + 1;
                             
            // exchanging the coordinates x with y of both
            // knight and target will result in same ans.
            dp[abs(y - ty)][abs(x - tx)] = 
                           dp[abs(x - tx)][abs(y - ty)];
            return dp[abs(x - tx)][abs(y - ty)];
        }
    }
}
  
// Driver Code
int main()
{
    int i, n, x, y, tx, ty, ans;
      
    // size of chess board n*n
    n = 100;
      
    // (x, y) coordinate of the knight.
    // (tx, ty) coordinate of the target position.
    x = 4;
    y = 5;
    tx = 1;
    ty = 1;
  
    // (Exception) these are the four corner points 
    // for which the minimum steps is 4.
    if ((x == 1 && y == 1 && tx == 2 && ty == 2) || 
        (x == 2 && y == 2 && tx == 1 && ty == 1))
            ans = 4;
    else if ((x == 1 && y == n && tx == 2 && ty == n - 1) ||
             (x == 2 && y == n - 1 && tx == 1 && ty == n))
                ans = 4;
    else if ((x == n && y == 1 && tx == n - 1 && ty == 2) || 
             (x == n - 1 && y == 2 && tx == n && ty == 1))
                ans = 4;
    else if ((x == n && y == n && tx == n - 1 && ty == n - 1) || 
             (x == n - 1 && y == n - 1 && tx == n && ty == n))
                ans = 4;
    else {
        // dp[a][b], here a, b is the difference of
        // x & tx and y & ty respectively.
        dp[1][0] = 3;
        dp[0][1] = 3;
        dp[1][1] = 2;
        dp[2][0] = 2;
        dp[0][2] = 2;
        dp[2][1] = 1;
        dp[1][2] = 1;
  
        ans = getsteps(x, y, tx, ty);
    }
  
    cout << ans << endl;
  
    return 0;
}

Java

//Java code for minimum steps for 
// a knight to reach target position 
public class GFG {
  
// initializing the matrix. 
    static int dp[][] = new int[8][8];
  
    static int getsteps(int x, int y,
            int tx, int ty) {
        // if knight is on the target 
        // position return 0. 
        if (x == tx && y == ty) {
            return dp[0][0];
        } else // if already calculated then return 
        // that value. Taking absolute difference. 
        if (dp[ Math.abs(x - tx)][ Math.abs(y - ty)] != 0) {
            return dp[ Math.abs(x - tx)][ Math.abs(y - ty)];
        } else {
  
            // there will be two distinct positions 
            // from the knight towards a target. 
            // if the target is in same row or column 
            // as of knight than there can be four 
            // positions towards the target but in that 
            // two would be the same and the other two 
            // would be the same. 
            int x1, y1, x2, y2;
  
            // (x1, y1) and (x2, y2) are two positions. 
            // these can be different according to situation. 
            // From position of knight, the chess board can be 
            // divided into four blocks i.e.. N-E, E-S, S-W, W-N . 
            if (x <= tx) {
                if (y <= ty) {
                    x1 = x + 2;
                    y1 = y + 1;
                    x2 = x + 1;
                    y2 = y + 2;
                } else {
                    x1 = x + 2;
                    y1 = y - 1;
                    x2 = x + 1;
                    y2 = y - 2;
                }
            } else if (y <= ty) {
                x1 = x - 2;
                y1 = y + 1;
                x2 = x - 1;
                y2 = y + 2;
            } else {
                x1 = x - 2;
                y1 = y - 1;
                x2 = x - 1;
                y2 = y - 2;
            }
  
            // ans will be, 1 + minimum of steps 
            // required from (x1, y1) and (x2, y2). 
            dp[ Math.abs(x - tx)][ Math.abs(y - ty)]
                    = Math.min(getsteps(x1, y1, tx, ty),
                            getsteps(x2, y2, tx, ty)) + 1;
  
            // exchanging the coordinates x with y of both 
            // knight and target will result in same ans. 
            dp[ Math.abs(y - ty)][ Math.abs(x - tx)]
                    = dp[ Math.abs(x - tx)][ Math.abs(y - ty)];
            return dp[ Math.abs(x - tx)][ Math.abs(y - ty)];
        }
    }
  
// Driver Code 
    static public void main(String[] args) {
        int i, n, x, y, tx, ty, ans;
  
        // size of chess board n*n 
        n = 100;
  
        // (x, y) coordinate of the knight. 
        // (tx, ty) coordinate of the target position. 
        x = 4;
        y = 5;
        tx = 1;
        ty = 1;
  
        // (Exception) these are the four corner points 
        // for which the minimum steps is 4. 
        if ((x == 1 && y == 1 && tx == 2 && ty == 2)
                || (x == 2 && y == 2 && tx == 1 && ty == 1)) {
            ans = 4;
        } else if ((x == 1 && y == n && tx == 2 && ty == n - 1)
                || (x == 2 && y == n - 1 && tx == 1 && ty == n)) {
            ans = 4;
        } else if ((x == n && y == 1 && tx == n - 1 && ty == 2)
                || (x == n - 1 && y == 2 && tx == n && ty == 1)) {
            ans = 4;
        } else if ((x == n && y == n && tx == n - 1 && ty == n - 1)
                || (x == n - 1 && y == n - 1 && tx == n && ty == n)) {
            ans = 4;
        } else {
            // dp[a][b], here a, b is the difference of 
            // x & tx and y & ty respectively. 
            dp[1][0] = 3;
            dp[0][1] = 3;
            dp[1][1] = 2;
            dp[2][0] = 2;
            dp[0][2] = 2;
            dp[2][1] = 1;
            dp[1][2] = 1;
  
            ans = getsteps(x, y, tx, ty);
        }
  
        System.out.println(ans);
    }
}
  
/*This code is contributed by PrinciRaj1992*/

Python3

# Python3 code for minimum steps for
# a knight to reach target position
  
# initializing the matrix.
dp = [[0 for i in range(8)] for j in range(8)];
  
  
def getsteps(x, y, tx, ty):
      
    # if knight is on the target
    # position return 0.
    if (x == tx and y == ty):
        return dp[0][0];
      
    # if already calculated then return
    # that value. Taking absolute difference.
    elif(dp[abs(x - tx)][abs(y - ty)] != 0):
        return dp[abs(x - tx)][abs(y - ty)];
    else:
  
        # there will be two distinct positions
        # from the knight towards a target.
        # if the target is in same row or column
        # as of knight than there can be four
        # positions towards the target but in that
        # two would be the same and the other two
        # would be the same.
        x1, y1, x2, y2 = 0, 0, 0, 0;
  
        # (x1, y1) and (x2, y2) are two positions.
        # these can be different according to situation.
        # From position of knight, the chess board can be
        # divided into four blocks i.e.. N-E, E-S, S-W, W-N .
        if (x <= tx):
            if (y <= ty):
                x1 = x + 2;
                y1 = y + 1;
         &n
Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022
Amazon SDE Sheet: вопросы и ответы на собеседовании
12 Декабря, 2022