Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
2.1.1.
Input
2.1.2.
Output
2.1.3.
Explanation 
3.
Intuition
4.
BFS Approach
4.1.
Algorithm
5.
Code
5.1.
C++
5.2.
Python
5.3.
Input
5.4.
Output
6.
Complexity Analysis 
6.1.
Time Complexity:
6.2.
Auxiliary Space
7.
Frequently Asked Questions
7.1.
How do I extract every route from a directed acyclic graph?
7.2.
How does graph theory determine the path?
7.3.
How do you tell if a graph component is tightly connected?
7.4.
How does walk graph theory work?
7.5.
How do you determine whether a graph has strong connections?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

Minimum steps to reach target

Author Saksham Gupta
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Graphs form the backbone of any coding interview. Thus it's essential to have a good grasp on the topic. Ninjas are here to help you, and  Here, we'll understand a problem: Minimum steps to reach the target. We will implement the program in different languages. 

Knight Problem Introduction

 

Problem Statement

A chessboard with squares that measure "N x N" has been given to you. The target position coordinates and the Knight's initial position coordinates are provided.

Your objective is to determine the shortest distance a Knight will travel to get to the desired location. Let's understand this better by an example.

Example

Input

Initial Position - {3, 4}
Final Position- {2, 1}

Output

2


Explanation 

Explanation

The knight can switch between places (1,3), (2,2), and (4,2) from  (3,4). Position (4, 2) is chosen, and the 'step_Count' value is changed to 1. The knight can hop immediately from location (4,2) to position (2,1), the target point, and 'step_Count' changes to 2, which is the answer. ('step_Count' is our step count variable).

Intuition

The problem is very much similar to the Shortest path in an unweighted graph. In the given problem also, if we consider two adjacent cells(cells in which our knight can jump) as adjacent vertices, then our problem will be a replica of the Shortest path in an unweighted graph problem which BFS solves because the edges are unweighted.

BFS Approach

The goal is to traverse the graph using BFS. Begin with the Knight's initial position and work your way through the cells. A queue is used for traversal. The queue saves the various paths taken by the knight as well as the number of steps taken. When the target is selected from the queue, the answer is the corresponding step count. Let's see the algorithm for a better understanding.

BFS

Algorithm

  • Create a class with the following data members:
    • 'X COORDINATE' to represent the x-coordinate.
    • 'Y COORDINATE' indicates the y-coordinate.
    • The value ''step_Count'' shows the number of steps.
  • Take two arrays, 'DIRECTION X' and 'DIRECTION Y,' which store the possible movement directions for the knight.
  • To keep the class objects, create a queue.
  • Take a visited array and set it to false to mark the cells that have already been called.
  • Push the knight's initial position to the queue and mark it as visited.
  • Continue the process until the queue is not empty.
  • Remove the front component.
    • If the current cell equals the target cell, return 'STEP COUNT,' which is the minor step a Knight will take to reach the target position.
    •  Otherwise, loop through all of the reachable coordinates. If the coordinate has not yet been visited and is reachable, add it to the queue along with the value of 'STEP COUNT' that has been incremented.

Now let us look at the code.

Code

C++

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


struct Cell {
    int x_Coordinate, y_Coordinate;
    int step_Count;
    Cell() {}
    Cell(int x, int y, int step) {
        x_Coordinate = x;
        y_Coordinate = y;
        step_Count = step;
    }
};


// Utility method returns true if (x, y) lies inside Board.
bool is_Inside(int x, int y, int n) {
    if (x >= 1 && x <= n && y >= 1 && y <= n) {
        return true;
    }
    return false;
}


int min_Steps(pair<int, int> knight_Position, pair<int, int> target_Position, int size) {
    // x and y direction, where a knight can move.
    int directionX[] = {-2, -1, 1, 2, -2, -1, 1, 2};
    int directionY[] = {-1, -2, -2, -1, 1, 2, 2, 1};


    // Queue for storing states of the knight in the board.
    queue<Cell> q;


    q.push(Cell(knight_Position.first, knight_Position.second, 0));
    Cell temp;
    int x, y;
    bool visited[size + 1][size + 1];


    // Make all the cells unvisited.
    for (int i = 1; i <= size; i++) {
        for (int j = 1; j <= size; j++) {
            visited[i][j] = false;
        }
    }


    visited[knight_Position.first][knight_Position.second] = true;
    while (!q.empty()) {
        temp = q.front();
        q.pop();


        // If the current cell is equal to the target cell, return its distance.
        if (temp.x_Coordinate == target_Position.first && temp.y_Coordinate == target_Position.second) {
            return temp.step_Count;
        }


        // Loop for all reachable states.
        for (int i = 0; i < 8; i++) {
            x = temp.x_Coordinate + directionX[i];
            y = temp.y_Coordinate + directionY[i];


            /* 
             If the reachable state is not yet visited and
                inside the board, push that state into the queue.
            */
            if (is_Inside(x, y, size) && !visited[x][y]) {
                visited[x][y] = true;
                q.push(Cell(x, y, temp.step_Count + 1));
            }
        }
    }
}
int main()
{
    // No of test cases.
    int t;
    cin>>t;
    while(t--)
    {
        // Size.
        int n;
        cin>>n;
        
        // Initial Positions.
        int stx,sty;
        cin>>stx>>sty;
        
        // Target Position
        int enx,eny;
        cin>>enx>>eny;
        cout<<min_Steps({stx,sty},{enx,eny},n)<<endl;
    }
}

Python

from sys import stdin
import sys
from collections import deque

class Cell:
    def __init__(self, x, y, step):
        self.x_Coordinate = x
        self.y_Coordinate = y
        self.step_Count = step



# Utility method returns true if (x, y) lies inside Board.
def is_Inside(x,  y,  n):
    if (x >= 1 and x <= n and y >= 1 and y <= n):
        return True
    return False

def min_Steps(kx, ky, tx, ty, size):
    # x and y direction, where a knight can move.
    directionX = [-2, -1, 1, 2, -2, -1, 1, 2]
    directionY = [-1, -2, -2, -1, 1, 2, 2, 1]


    # Queue for storing states of the knight in the board.
    q = deque()

    q.append(Cell(kx, ky, 0))
    visited = [[False for i in range(size+2)] for j in range(size+2)]


    # Make all the cells unvisited.
    for i in range(1, size+1):
        for j in range(1, size+1):
            visited[i][j] = False


    visited[kx][ky] = True
    while (len(q) != 0):
        temp = q.popleft()


        # If the current cell equals the target cell, return its distance.
        if (temp.x_Coordinate == tx and temp.y_Coordinate == ty):
            return temp.step_Count


        # Loop for all reachable states.
        for i in range(0, 8):
            x = temp.x_Coordinate + directionX[i]
            y = temp.y_Coordinate + directionY[i]


            '''
                If the reachable state is not yet visited and
                inside the board, push that state into the queue 
            '''
            if (is_Inside(x, y, size) and not visited[x][y]):
                visited[x][y] = True
                q.append(Cell(x, y, temp.step_Count+1))

# Taking input using fast I/O.
def take_Input():
    size = int(input())

    kx, ky = list(map(int, input().strip().split(" ")))
    tx, ty = list(map(int, input().strip().split(" ")))

    return size, kx, ky, tx, ty

# Main.
t = int(input())
while t:
    size, kx, ky, tx, ty = take_Input()
    print(min_Steps(kx, ky, tx, ty, size))
    t = t-1

Input

2
8
2 1
8 5
6
4 5
1 1

Output

4
3

Complexity Analysis 

Time Complexity:

O(N * N), where N is the size of the matrix.

Explanation:

This is because, In the worst case, all the cells will be visited, and as the total number of cells is N * N, the time complexity is O (N * N)

Auxiliary Space

O(N * N), where N is the size of the matrix.

Explanation: 

In the worst case, all nodes will be stored in the queue.

Frequently Asked Questions

How do I extract every route from a directed acyclic graph?

Using exponential, find every potential path across any graph. Backtracking can be used to fix the problem. We may use Depth First Search for DAGs (DFS). Start from any node in the DFS code, travel to the furthest dead end, and use an array or list to record all the nodes you visited along the way.

How does graph theory determine the path?

Finding a path between two vertices may be done using either a depth-first search (DFS) or a breadth-first search (BFS). In BFS (or DFS), use the first vertex as a source and proceed as normal (or DFS). Return true if our traverse finds the second vertex; otherwise, return false.

How do you tell if a graph component is tightly connected?

A directed graph is said to be highly linked if there is a path connecting each pair of the graph's vertices in each direction. The first vertex in the pair has a way leading to the second, and the second vertex has a path leading to the first.

How does walk graph theory work?

A walk is a collection of vertices and edges in a graph. A traversal of a graph is referred to as a "walk" after it is completed. There may be repeated vertices and edges in a walk. The length of a stroll is determined by how many edges are covered in it.

How do you determine whether a graph has strong connections?

Conducting a Depth-first search (DFS) or a Breadth-first search (BFS) beginning at each graph vertex is a straightforward solution. The graph is tightly linked if each DFS/BFS call reaches every other vertex in the graph.

Conclusion

In this blog, we understood the problem ‘Minimum steps to reach target’.We implemented the program in different languages using Breadth-first search.  

Check out these questions. It will help you in exploring path-finding algorithms similar to BFS.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow. 

Comment here with any questions or concerns you may have about the post.

Happy Learning Ninja! 

Live masterclass