Do you think IIT Guwahati certified course can help you in your career?
No
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.
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
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.
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.