Мінімальныя крокі для дасягнення мэты рыцарам


Узровень складанасці Жорсткі
Часта пытаюцца ў амазонка LinkedIn MakeMyTrip
Шырыня Першы пошук Дынамічнае праграмаванне Графік чаргу

апісанне

Праблема «Мінімальныя крокі для дасягнення мэты рыцарам» абвяшчае, што вам даецца квадратная шахматная дошка памерам N x N, каардынаты фігуры рыцара і ячэйка-мішэнь. Даведайцеся мінімальную колькасць крокаў, зробленых фігурай Рыцара, каб дасягнуць мэтавай клеткі.

Рыцарскія прыступкі: У адпаведнасці з правіламі шахмат, рыцар перамяшчае 2 квадрата ў адзін бок і 1 квадрат у перпендыкулярным кірунку (ці наадварот).

Прыклад

(kx,ky) = (1,1) & (tx,ty) = (15,15)
Minimum number of moves = 10
(kx,ky) = (2,8) & (tx,ty) = (8,4)
Minimum number of moves = 4
(kx,ky) = (2,8) & (tx,ty) = (8,4)
Minimum number of moves = 4

Мінімальныя крокі для дасягнення мэты рыцарам

 

Віды рашэння

  1. Шырыня Першы пошук

  2. Дынамічнае праграмаванне

Шырыня Першы пошук

Падыход

Ідэя складаецца ў тым, каб выступіць BFS пачынаючы з пачатковай пазіцыі рыцара. Мы пераходзім да ўсіх наступных ячэек (і іх наступных ячэек) ітэрацыйна з зададзенага становішча (альбо каардынатаў), кожная з наступных ячэек наведваецца ў Рыцарскія крокі манера. Абыход выконваецца з выкарыстаннем чаргі BFS, кожны вузел чаргі захоўвае каардынаты ячэйкі, сустрэтыя падчас праходжання BFS, а таксама колькасць крокаў, зробленых для дасягнення гэтай канкрэтнай ячэйкі. Пасля таго, як мэтавая ячэйка выскачыць з чаргі BFS, значэнне колькасці крокаў з'яўляецца неабходным адказам.

Алгарытм

1. Define a class that has following data variables:
    1. x: to store x-coordinate of the cell.
    2. y: to store y-coordinate of the cell.
    3. steps: number of steps required to reach that cell starting from co-ordinates of the Knight.
2. Create a BFS queue that stores class objects as nodes.
3. Begin the Iterative BFS traversal.
4. In every step of the iterative traversal, pop a node from the queue. say,the node is front.
5. If the cell at coordinates (front.y, front.x) is the target cell, return the value of front.steps.
    1. Else, continue the iterative traversal.

Мінімальныя крокі для дасягнення мэты рыцарам

Мінімальныя крокі для дасягнення мэты рыцарам

код

Праграма C ++ для пошуку мінімальных крокаў для дасягнення мэты рыцарам

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// definition of queue node
class Node
{
    public:
    // y-coordinate
    int y;
    // x-coordinate
    int x;
    // number of steps to reach (y,x)
    int steps;
    
    // constructor
    Node(int i,int j,int moves)
    {
        y = i;
        x = j;
        steps = moves;
    }
};

// traversal array along rows
int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
// traversal array along columns
int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1}; 

// BFS to return number of steps required to reach from source to target
int BFS(Node source, Node target, int N)
{
    // set to mark a cell as visited
    unordered_set <string> visited;
    // BFS queue
    queue <Node> q;
    // push the source node
    q.push(source);
    
    // BFS traversal 
    while(!q.empty())
    {
        Node front = q.front();
        q.pop(); 
        
        // if target coordinate is reached
        if(front.y == target.y && front.x == target.x)
        return front.steps;
        
        // traverse all neighbors of current cell
        for(int i=0;i<8;i++)
        {
            int next_y = front.y + dy[i];
            int next_x = front.x + dx[i];
            
            // store coordinates of a cell as string
            string search = to_string(next_y) + '|' + to_string(next_x);
            
            // move to neighbor cell if it is not visited lies within the N x N chessboard
            if(visited.find(search) == visited.end() && next_y > 0 && next_x > 0 && next_y <= N && next_x <= N)
            {
                Node next(next_y,next_x,front.steps+1);
                q.push(next);
                visited.insert(search);
            }
        }
    }
}

int main()
{
    // dimensions of the square chessboard
    int N = 8;
    // coordinates of source & target cell
    Node source(2,8,0), target(8,4,-1);
    cout<<"Number of steps : "<<BFS(source,target,N)<<endl;
    return 0;
}
Number of steps : 4

Праграма Java для пошуку мінімальных крокаў для дасягнення мэты рыцарам

import java.util.*;
import java.io.*;

class TutorialCup 
{
    // definition of queue node
    static class Node
    {
        // y-coordinate
        int y;
        // x-coordinate
        int x;
        // number of steps to reach (y,x)
        int steps;
        
        // constructor
        Node(int i,int j,int moves)
        {
            y = i;
            x = j;
            steps = moves;
        }
    };
    
    // traversal array along rows
    static int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
    // traversal array along columns
    static int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1}; 
    
    // BFS to return number of steps required to reach from source to target
    static int BFS(Node source, Node target, int N)
    {
        // set to mark a cell as visited
        HashSet <String> visited = new HashSet<>();
        // BFS queue
        Queue <Node> q = new LinkedList<>();
        // push the source node
        q.add(source);
        
        // BFS traversal 
        while(!q.isEmpty())
        {
            Node front = q.poll();
            
            // if target coordinate is reached
            if(front.y == target.y && front.x == target.x)
            return front.steps;
            
            // traverse all neighbors of current cell
            for(int i=0;i<8;i++)
            {
                int next_y = front.y + dy[i];
                int next_x = front.x + dx[i];
                
                // store coordinates of a cell as string
                String search = next_y + "|" + next_x;
                
                // move to neighbor cell if it is not visited lies within the N x N chessboard
                if(visited.contains(search) == false && next_y > 0 && next_x > 0 && next_y <= N && next_x <= N)
                {
                    Node next = new Node(next_y,next_x,front.steps+1);
                    q.add(next);
                    visited.add(search);
                }
            }
        }
        return 0;
    }
    public static void main (String[] args)
    {
        // dimensions of the square chessboard
        int N = 8;
        // coordinates of source & target cell
        Node source = new Node(2,8,0);
        Node target = new Node(8,4,-1);
        System.out.println("Number of steps : "+BFS(source,target,N));
    }
}
Number of steps : 4

Аналіз складанасці

  1. Складанасць часу: T (n) = O (N ^ 2)
    Таму што ў нас квадратная матрыца і ў горшым выпадку. Такім чынам, нам, магчыма, давядзецца мець справу з кожнай з клетак. І вось як дасягаецца квадратычная складанасць часу.
  2. Складанасць прасторы: A (n) = O (N ^ 2)
    Тут мы выкарысталі BFS, з-за чаго алгарытм мае шматскладовую прасторавую складанасць.

Дынамічнае праграмаванне

Падыход

Разгледзім прыведзеныя ніжэй пункты, каб зразумець праблемны падыход:

Разгледзім здагадкі, зробленыя ніжэй:

  1. Шахматная дошка ўяўляе сабой стандартны квадрат N х N.
  2. kx & ky - каардынаты рыцара.
  3. tx & ty - каардынаты ячэйкі Target.

 

Нелінейныя пазіцыі : Калі ячэйка рыцара і мэты знаходзіцца па розных радках і слупках. г.зн. kx не = tx & ky не = ці.

  1. напрыклад: (kx, ky) = (3,3) & (tx, ty) = (6,6)
  2. Да мэты рухаюцца толькі 2 прыступкі:
    • (3,3) -> (4,5) і (3,3) -> (5,4)
  3. Такім чынам, выкарыстоўваючы дынамічнае праграмаванне, minSteps {(3,3) to (6,6)} = 1 + [minSteps {(4,5) to (6,6)}} or minSteps {(5,4) - (6,6)}]

Мінімальныя крокі для дасягнення мэты рыцарам

Лінейныя пазіцыі : Калі ячэйка рыцара і мэты знаходзіцца ўздоўж альбо таго ж радка, альбо слупкоў. г. зн. альбо kx = tx or ky = ty.

  1. напрыклад: (kx, ky) = (2,4) & (tx, ty) = (7,4)
  2. Усяго да мэты ёсць 4 крокі, якія:
    • (2,4) -> (4,5) і (2,4) -> (4,3), абодва гэтыя этапы эквівалентныя
    • (2,4) -> (3,6) і (2,4) -> (3,2), абодва гэтыя этапы эквівалентныя
  3. Такім чынам, выкарыстоўваючы дынамічнае праграмаванне, minКрокі {(2,4) да (7,4)} = 1 + мін[minКрокі {(2,4) да (4,5)} , minКрокі {(2,4) да (3,6)}].

Мінімальныя крокі для дасягнення мэты рыцарам

Кутнія выпадкі : Калі хто-небудзь з рыцара ці мэты знаходзіцца на рагу і [ABS(kх-тх) , абс(kу-ты)] = [1,1]. Тады мінімальныя крокі для дасягнення мэты будуць 4.

Наступны фрагмент кода пазначае базавыя выпадкі:

Базавыя справы : базавыя выпадкі разглядаюцца ніжэй:

Наступны фрагмент кода пазначае базавыя выпадкі:

,en Дынамічнае праграмаванне Ураўненне з выкарыстаннем табліцы становіцца:

  1. табліца [abs (kx - tx)] [abs (ky - ty)] = мінімальная колькасць крокаў, каб перайсці ад рыцарскай пазіцыі (kx, ky) да мэтавай пазіцыі (tx, ty).
  2. табліца [abs (kx - tx)] [abs (ky - ty)] = табліца [abs (ky - ty)] [abs (kx - tx)].

Алгарытм

1. Define the solution for corner cases. i.e. when the knight or target are at 4 corners of the board and difference in their positions are (1,1). The minimum number of moves from source to target is 4. These positions are depicted below:
2. Define the base cases as discussed below:
    1. when the Knight & target are at adjacent squares (along the same row/column), minimum number of moves required to reach the destination is 3.
    2. when the Knight & target are at adjacent squares but lie diagonally to each other, minimum number of moves required to reach the destinations is 2.
    3. when Knight & target are at positions as depicted in the image, minimum number of moves required to reach destination is 1.
    4. If the Knight & target are at same position, minimum number of moves required is 0.
3. For any other case, refer Linear Positions & Non-Linear Positions in the approach section.

код

Праграма C ++ для пошуку мінімальных крокаў для дасягнення мэты рыцарам

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int minStepsRecur(int kx, int ky, int tx, int ty, vector<vector<int>>& table) 
{ 
    // when Knight & Target are at same position
    if (kx == tx && ky == ty) 
        return table[0][0];
    
    else 
    { 
        // if value in the table has been calculated already
        if (table[abs(kx - tx)][abs(ky - ty)] != 0) 
            return table[abs(kx - tx)][abs(ky - ty)]; 
            
        // Linear Positions
        /* Knight can move to -->2 different squares<-- that goes towards the Target */
        
        // Non-Linear Positions
        /* Knight can move to 4 different squares that 
        goes towards the Target of which -->2 are equivalent<-- */
        
        // For every position of Knight & Target 
        // there are 2 different positions i.e. (x1,y1) & (x2,y2), the Knight can move to. 
        else 
        { 
  
            int x1, y1, x2, y2; 
              
            // the values of (x1,y1) & (x2,y2) depend upon relative positions of Knight & Target
            // (x1,y1) & (x2,y2) are midway between (kx,ky) & (tx,ty)
            // Their calculations are made accordingly
            if (kx <= tx) 
            { 
                if (ky <= ty) 
                { 
                    x1 = kx + 2; 
                    y1 = ky + 1; 
                    x2 = kx + 1; 
                    y2 = ky + 2; 
                } 
                else 
                { 
                    x1 = kx + 2; 
                    y1 = ky - 1; 
                    x2 = kx + 1; 
                    y2 = ky - 2; 
                } 
            } 
            
            else 
            { 
                if (ky <= ty) 
                { 
                    x1 = kx - 2; 
                    y1 = ky + 1; 
                    x2 = kx - 1; 
                    y2 = ky + 2; 
                } 
                else 
                { 
                    x1 = kx - 2; 
                    y1 = ky - 1; 
                    x2 = kx - 1; 
                    y2 = ky - 2; 
                } 
            } 
              
            // The minimum steps from (kx,ky) to (tx,ty) = 1 + minimum of steps from (x1, y1) to (x2, y2). 
            table[abs(kx - tx)][abs(ky - ty)] = 1 + min(minStepsRecur(x1, y1, tx, ty, table),minStepsRecur(x2, y2, tx, ty, table)); 
                             
            // exchanging the coordinates x with y of both knight and target will result in same min moves. 
            table[abs(ky - ty)][abs(kx - tx)] = table[abs(kx - tx)][abs(ky - ty)];
            
            return table[abs(kx - tx)][abs(ky - ty)]; 
        } 
    } 
} 

int minSteps(int kx, int ky, int tx, int ty, int n)
{
    // Corner Cases
    if ((kx == 1 && ky == 1 && tx == 2 && ty == 2) || (kx == 2 && ky == 2 && tx == 1 && ty == 1)) 
        return 4; 
    
    else if ((kx == 1 && ky == n && tx == 2 && ty == n - 1) || (kx == 2 && ky == n - 1 && tx == 1 && ty == n)) 
        return 4; 
    
    else if ((kx == n && ky == 1 && tx == n - 1 && ty == 2) || (kx == n - 1 && ky == 2 && tx == n && ty == 1)) 
        return 4; 
    
    else if ((kx == n && ky == n && tx == n - 1 && ty == n - 1) || (kx == n - 1 && ky == n - 1 && tx == n && ty == n)) 
        return 4;
    
    else 
    {
        vector <int> row(20,0);
        vector <vector<int>> table;
        

        for(int i=0; i<20; i++)
        table.push_back(row);
        
        // Base Cases
        table[2][1] = 1; 
        table[1][2] = 1; 
        
        table[1][1] = 2; 
        table[2][0] = 2; 
        table[0][2] = 2;
        
        table[1][0] = 3; 
        table[0][1] = 3; 
        
       
        // Linear & Non-Linear positions
        return minStepsRecur(kx, ky, tx, ty, table);
    } 
}

int main()
{
    int n = 8;
    int kx = 2, ky = 8, tx = 8, ty = 4;
    
    cout<<"Number of steps : "<<minSteps(kx,ky,tx,ty,n)<<endl;
    return 0;
}
Number of steps : 4

Праграма Java для пошуку мінімальных крокаў для дасягнення мэты рыцарам

import java.util.*;
import java.io.*;

class TutorialCup
{
    static int minStepsRecur(int kx, int ky, int tx, int ty, int [][] table) 
    { 
        // when Knight & Target are at same position
        if (kx == tx && ky == ty) 
            return table[0][0];
        
        else 
        { 
            // if value in the table has been calculated already
            if (table[Math.abs(kx - tx)][Math.abs(ky - ty)] != 0) 
                return table[Math.abs(kx - tx)][Math.abs(ky - ty)]; 
                
            // Linear Positions
            /* Knight can move to -->2 different squares<-- that goes towards the Target */
            
            // Non-Linear Positions
            /* Knight can move to 4 different squares that 
            goes towards the Target of which -->2 are equivalent<-- */
            
            // For every position of Knight & Target 
            // there are 2 different positions i.e. (x1,y1) & (x2,y2), the Knight can move to. 
            else 
            { 
      
                int x1, y1, x2, y2; 
                  
                // the values of (x1,y1) & (x2,y2) depend upon relative positions of Knight & Target
                // (x1,y1) & (x2,y2) are midway between (kx,ky) & (tx,ty)
                // Their calculations are made accordingly
                if (kx <= tx) 
                { 
                    if (ky <= ty) 
                    { 
                        x1 = kx + 2; 
                        y1 = ky + 1; 
                        x2 = kx + 1; 
                        y2 = ky + 2; 
                    } 
                    else 
                    { 
                        x1 = kx + 2; 
                        y1 = ky - 1; 
                        x2 = kx + 1; 
                        y2 = ky - 2; 
                    } 
                } 
                
                else 
                { 
                    if (ky <= ty) 
                    { 
                        x1 = kx - 2; 
                        y1 = ky + 1; 
                        x2 = kx - 1; 
                        y2 = ky + 2; 
                    } 
                    else 
                    { 
                        x1 = kx - 2; 
                        y1 = ky - 1; 
                        x2 = kx - 1; 
                        y2 = ky - 2; 
                    } 
                } 
                  
                // The minimum steps from (kx,ky) to (tx,ty) = 1 + minimum of steps from (x1, y1) to (x2, y2). 
                table[Math.abs(kx - tx)][Math.abs(ky - ty)] = 1 + Math.min(minStepsRecur(x1, y1, tx, ty, table),minStepsRecur(x2, y2, tx, ty, table)); 
                                 
                // exchanging the coordinates x with y of both knight and target will result in same min moves. 
                table[Math.abs(ky - ty)][Math.abs(kx - tx)] = table[Math.abs(kx - tx)][Math.abs(ky - ty)];
                
                return table[Math.abs(kx - tx)][Math.abs(ky - ty)]; 
            } 
        } 
    } 

    static int minSteps(int kx, int ky, int tx, int ty, int n)
    {
        // Corner Cases
        if ((kx == 1 && ky == 1 && tx == 2 && ty == 2) || (kx == 2 && ky == 2 && tx == 1 && ty == 1)) 
            return 4; 
        
        else if ((kx == 1 && ky == n && tx == 2 && ty == n - 1) || (kx == 2 && ky == n - 1 && tx == 1 && ty == n)) 
            return 4; 
        
        else if ((kx == n && ky == 1 && tx == n - 1 && ty == 2) || (kx == n - 1 && ky == 2 && tx == n && ty == 1)) 
            return 4; 
        
        else if ((kx == n && ky == n && tx == n - 1 && ty == n - 1) || (kx == n - 1 && ky == n - 1 && tx == n && ty == n)) 
            return 4;
        
        else 
        {
            int [][] table = new int[20][20];
            
            // Base Cases
            table[2][1] = 1; 
            table[1][2] = 1; 
            
            table[1][1] = 2; 
            table[2][0] = 2; 
            table[0][2] = 2;
            
            table[1][0] = 3; 
            table[0][1] = 3; 
            
           
            // Linear & Non-Linear positions
            return minStepsRecur(kx, ky, tx, ty, table);
        } 
    }
    
    public static void main (String[] args) 
    {
        int n = 8;
        int kx = 2, ky = 8, tx = 8, ty = 4;
        
        System.out.println("Number of steps : "+minSteps(kx,ky,tx,ty,n));
    }
}
Number of steps : 4

Аналіз складанасці

  1. Складанасць часу: T (n) = O [abs ( (kx-tx) * (ky-ty) )]
    Паколькі мы маем справу толькі з клеткамі, якія ўваходзяць у падматрыцу, сфармаваную з пачатковай і мэтавай ячэйкі. Такім чынам, нягледзячы на ​​тое, што гэта рашэнне таксама мае квадратычную складанасць у часе, аналагічную вышэйапісанаму рашэнню.
  2. Касмічная складанасць: A (n) = O [abs ( (kx-tx) * (ky-ty) )]

дзе,

  1. (kx, ky) = пазіцыя рыцара
  2. (tx, ty) = становішча ячэйкі-мэты