Data Modelling & AI Data Structure & Algorithm

Shortest path between two points in a Matrix with at most K obstacles

23 June 2025

0

Given a 2-D array matrix[][] of size ROW * COL and an integer K, where each cell matrix[i][j] is either 0 (empty) or 1 (obstacle). A pointer can move up, down, left, or right from and to an empty cell in a single step. The task is to find the minimum number of steps required to go from the source (0, 0) to the destination (ROW-1, COL-1) with less than or equal to K obstacle eliminations. An obstacle elimination is defined as changing a cell’s value matrix[i][j] from 1 to 0. If no path is possible then return -1.

Examples:

Input: matrix[][] = { {0,0,1},
{1,0,1},
{0,1,0} },
ROW = 3, COL = 3, K = 2
Output: 4
Explanation:

Change the value of matrix[0][2] and matrix[1][2] to 0 and the path is 0,0 -> 0,1 -> 0,2 -> 1,2 -> 2,2.

Input: matrix[][] = { {0,1,0},
{1,1,0},
{0,0,0},
{0,0,0} },
ROW = 4, COL = 3, K = 1
Output: 5

Approach: The shortest path can be searched using BFS on a Matrix. Initialize a counter[][] vector, this array will keep track of the number of remaining obstacles that can be eliminated for each visited cell. Run a Breadth-first search on each cell and while keeping track of the number of obstacles we can still eliminate. At each cell, first, check if it is the destination cell or not. Then, it is checked if the current cell is an obstacle then the count of eliminations available is decremented by 1. If the cell value in the counter array has a lower value than the current variable then it is updated. The length array is updated at every step. Follow the steps below to solve the problem:

Define 2 arrays dir_Row[4] and dir_Col[4] to store the direction coordinates possible from each point.
Define a structure pointLoc as x, y, and k.
Initialize a queue q[] of pointLoc datatype.
Initialize a 2-D vector distance[ROW][COL] with values 0 to store the distance of each cell from the source cell.
Initialize a 2-D vector obstackles[ROW][COL] with values -1 to store the count of available obstacle eliminations.
Enqueue the value {0, 0, K} into the queue q[].
Traverse in a while loop till the size of the queue q[] is greater than 0 and perform the following tasks:
- Initialize a variable te as the front of the queue q[].
- Initialize the variables x, y and tk as te.x, te.y and te.k.
- If the current cell equals the destination cell, then return the value of distance[x][y] as the answer.
- Dequeue the front element from the queue q[].
- If the current cell is an obstacle then if tk is greater than 0 then decrease its value by 1 else continue.
- If obstacles[x][y] is greater than equal to tk then continue else set its value as tk.
- Iterate over the range [0, 4) using the variable i and perform the following tasks:
  - See all the neighboring cells (ax, ay) and check if they are valid cells or not. If not, then continue. Else enqueue {ax, ay, tk} into the queue q[] and set the value of distance[ax][ay] as distance[x][y] + 1.
After performing the above steps, print the value -1 if no answer is found.

Below is the implementation of the above approach.

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
#define ROW 3
#define COL 3
 
// Direction Vectors
int dir_Row[4] = { -1, 0, 1, 0 };
int dir_Col[4] = { 0, 1, 0, -1 };
 
// Structure for storing coordinates
// count of remaining obstacle eliminations
struct pointLoc {
    int x, y, k;
};
 
// Function to perform BFS
int BFS(int matrix[][COL], int k, pair<int, int> source,
        pair<int, int> destination)
{
 
    // Stores pointLoc of each cell
    queue<struct pointLoc> q;
 
    // Vector array to store distance of
    // each cell from source cell
    vector<vector<int> > distance(
      ROW, vector<int>(COL, 0));
 
    // Vector array to store count of
    // available obstacle eliminations
    vector<vector<int> > obstacles(
      ROW, vector<int>(COL, -1));
 
    // Push the source cell into queue
    // and use as starting point
    q.push({ source.first, source.second, k });
 
    // Iterate while queue is not empty
    while (!q.empty()) {
 
        struct pointLoc te = q.front();
        int x = te.x;
        int y = te.y;
        int tk = te.k;
 
        // If current cell is same as
        // destination then return distance
        if (x == destination.first
            && y == destination.second)
            return distance[x][y];
 
        q.pop();
 
        // If current cell is an obstacle
        // then decrement current value
        // if possible else skip the cell
        if (matrix[x][y] == 1) {
 
            if (tk > 0)
                tk--;
 
            else
                continue;
        }
 
        // Cell is skipped only if current
        // value is less than previous
        // value of cell
        if (obstacles[x][y] >= tk)
            continue;
 
        // Else update value
        obstacles[x][y] = tk;
 
        // Push all valid adjacent
        // cells into queue
        for (int i = 0; i < 4; i++) {
 
            int ax = x + dir_Row[i];
            int ay = y + dir_Col[i];
 
            if (ax < 0 || ay < 0 
                || ax >= ROW || ay >= COL)
                continue;
 
            q.push({ ax, ay, tk });
 
            // Update distance of current
            // cell from source cell
            distance[ax][ay] = distance[x][y] + 1;
        }
    }
 
    // If not possible to reach
    // destination from source
    return -1;
}
 
// Driver Code
int main()
{
 
    // Given input
    int matrix[ROW][COL]
        = { { 0, 0, 1 },
           { 1, 0, 1 },
           { 0, 1, 0 } };
 
    int k = 2;
 
    pair<int, int> source = { 0, 0 };
 
    pair<int, int> destination = { 2, 2 };
 
    cout << BFS(matrix, k, source, destination);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG {
 
    static final int ROW = 3;
    static final int COL = 3;
 
    // Direction Vectors
    static int dir_Row[] = { -1, 0, 1, 0 };
    static int dir_Col[] = { 0, 1, 0, -1 };
 
    // Structure for storing coordinates
    // count of remaining obstacle eliminations
    static class pointLoc {
        int x, y, k;
 
        public pointLoc(int x, int y, int k) {
            super();
            this.x = x;
            this.y = y;
            this.k = k;
        }
    };
 
    static class pair {
        int first, second;
 
        public pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
 
    // Function to perform BFS
    static int BFS(int matrix[][], int k, pair source, pair destination) {
 
        // Stores pointLoc of each cell
        Queue<pointLoc> q = new LinkedList<GFG.pointLoc>();
 
        // Vector array to store distance of
        // each cell from source cell
 
        int[][] distance = new int[ROW][COL];
 
        // Vector array to store count of
        // available obstacle eliminations
 
        int[][] obstacles = new int[ROW][COL];
 
        // Push the source cell into queue
        // and use as starting point
        q.add(new pointLoc(source.first, source.second, k));
 
        // Iterate while queue is not empty
        while (!q.isEmpty()) {
 
            pointLoc te = q.peek();
            int x = te.x;
            int y = te.y;
            int tk = te.k;
 
            // If current cell is same as
            // destination then return distance
            if (x == destination.first && y == destination.second)
                return distance[x][y];
 
            q.remove();
 
            // If current cell is an obstacle
            // then decrement current value
            // if possible else skip the cell
            if (matrix[x][y] == 1) {
 
                if (tk > 0)
                    tk--;
 
                else
                    continue;
            }
 
            // Cell is skipped only if current
            // value is less than previous
            // value of cell
            if (obstacles[x][y] >= tk)
                continue;
 
            // Else update value
            obstacles[x][y] = tk;
 
            // Push all valid adjacent
            // cells into queue
            for (int i = 0; i < 4; i++) {
 
                int ax = x + dir_Row[i];
                int ay = y + dir_Col[i];
 
                if (ax < 0 || ay < 0 || ax >= ROW || ay >= COL)
                    continue;
 
                q.add(new pointLoc(ax, ay, tk));
 
                // Update distance of current
                // cell from source cell
                distance[ax][ay] = distance[x][y] + 1;
            }
        }
 
        // If not possible to reach
        // destination from source
        return -1;
    }
 
    // Driver Code
    public static void main(String[] args) {
 
        // Given input
        int matrix[][] = { { 0, 0, 1 }, { 1, 0, 1 }, { 0, 1, 0 } };
        int k = 2;
        pair source = new pair(0, 0);
        pair destination = new pair(2, 2);
        System.out.print(BFS(matrix, k, source, destination));
    }
}
 
// This code is contributed by shikhasingrajput

Python3

# Python Program to implement
# the above approach
ROW = 3
COL = 3
 
# Direction Vectors
dir_Row = [-1, 0, 1, 0]
dir_Col = [0, 1, 0, -1]
 
# Structure for storing coordinates
# count of remaining obstacle eliminations
class pointLoc:
    def __init__(self,x, y, k):
        self.x = x
        self.y = y
        self.k = k
 
 
# Function to perform BFS
def BFS(matrix, k, source,destination):
 
    # Stores pointLoc of each cell
    q = []
 
    # Vector array to store distance of
    # each cell from source cell
    distance = [0 for i in range(ROW)]
 
    for i in range(len(distance)):
        distance[i] = [0 for i in range(COL)]
 
 
    # Vector array to store count of
    # available obstacle eliminations
    obstacles = [0 for i in range(ROW)]
    for i in range(len(obstacles)):
        obstacles[i] = [-1 for i in range(COL)]
 
    # Push the source cell into queue
    # and use as starting point
    q.append(pointLoc(source[0], source[1], k))
 
    # Iterate while queue is not empty
    while (len(q) > 0):
 
        te = q[0]
        x = te.x
        y = te.y
        tk = te.k
 
        # If current cell is same as
        # destination then return distance
        if (x == destination[0] and y == destination[1]):
            return distance[x][y]
 
        q = q[1:]
 
        # If current cell is an obstacle
        # then decrement current value
        # if possible else skip the cell
        if (matrix[x][y] == 1):
 
            if (tk > 0):
                tk -= 1
            else:
                continue
 
        # Cell is skipped only if current
        # value is less than previous
        # value of cell
        if (obstacles[x][y] >= tk):
            continue
 
        # Else update value
        obstacles[x][y] = tk
 
        # Push all valid adjacent
        # cells into queue
        for i in range(4):
 
            ax = x + dir_Row[i]
            ay = y + dir_Col[i]
 
            if (ax < 0 or ay < 0 or ax >= ROW or ay >= COL):
                continue
 
            q.append(pointLoc(ax, ay, tk))
 
            # Update distance of current
            # cell from source cell
            distance[ax][ay] = distance[x][y] + 1
 
    # If not possible to reach
    # destination from source
    return -1
 
# Driver Code
 
# Given input
matrix = [[0, 0, 1],[1, 0, 1],[0, 1, 0]]
 
k = 2
source = [0, 0]
destination = [2, 2]
print(BFS(matrix, k, source, destination))
 
# This code is contributed by shinjanpatra

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
static readonly int ROW = 3;
static readonly int COL = 3;
 
// Direction Lists
static int []dir_Row = { -1, 0, 1, 0 };
static int []dir_Col = { 0, 1, 0, -1 };
 
// Structure for storing coordinates
// count of remaining obstacle eliminations
class pointLoc 
{
    public int x, y, k;
     
    public pointLoc(int x, int y, int k) 
    {
        this.x = x;
        this.y = y;
        this.k = k;
    }
};
 
class pair 
{
    public int first, second;
 
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to perform BFS
static int BFS(int [,]matrix, int k, pair source,
               pair destination)
{
     
    // Stores pointLoc of each cell
    Queue<pointLoc> q = new Queue<GFG.pointLoc>();
 
    // List array to store distance of
    // each cell from source cell
    int[,] distance = new int[ROW, COL];
 
    // List array to store count of
    // available obstacle eliminations
    int[,] obstacles = new int[ROW, COL];
 
    // Push the source cell into queue
    // and use as starting point
    q.Enqueue(new pointLoc(source.first, 
                           source.second, k));
 
    // Iterate while queue is not empty
    while (q.Count != 0) 
    {
        pointLoc te = q.Peek();
        int x = te.x;
        int y = te.y;
        int tk = te.k;
         
        // If current cell is same as
        // destination then return distance
        if (x == destination.first &&
            y == destination.second)
            return distance[x, y];
 
        q.Dequeue();
 
        // If current cell is an obstacle
        // then decrement current value
        // if possible else skip the cell
        if (matrix[x, y] == 1) 
        {
            if (tk > 0)
                tk--;
            else
                continue;
        }
 
        // Cell is skipped only if current
        // value is less than previous
        // value of cell
        if (obstacles[x, y] >= tk)
            continue;
 
        // Else update value
        obstacles[x, y] = tk;
 
        // Push all valid adjacent
        // cells into queue
        for(int i = 0; i < 4; i++)
        {
            int ax = x + dir_Row[i];
            int ay = y + dir_Col[i];
 
            if (ax < 0 || ay < 0 || 
             ax >= ROW || ay >= COL)
                continue;
 
            q.Enqueue(new pointLoc(ax, ay, tk));
 
            // Update distance of current
            // cell from source cell
            distance[ax, ay] = distance[x, y] + 1;
        }
    }
 
    // If not possible to reach
    // destination from source
    return -1;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given input
    int [,]matrix = { { 0, 0, 1 }, 
                      { 1, 0, 1 }, 
                      { 0, 1, 0 } };
    int k = 2;
    pair source = new pair(0, 0);
    pair destination = new pair(2, 2);
     
    Console.Write(BFS(matrix, k, source, destination));
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
 
       // JavaScript Program to implement
       // the above approach 
       let ROW = 3
       let COL = 3
 
       // Direction Vectors
       let dir_Row = [-1, 0, 1, 0];
       let dir_Col = [0, 1, 0, -1];
 
       // Structure for storing coordinates
       // count of remaining obstacle eliminations
       class pointLoc {
           constructor(x, y, k) {
               this.x = x;
               this.y = y;
               this.k = k;
           }
 
       };
 
       // Function to perform BFS
       function BFS(matrix, k, source,
           destination) {
 
           // Stores pointLoc of each cell
           let q = [];
 
           // Vector array to store distance of
           // each cell from source cell
           let distance = new Array(ROW);
           for (let i = 0; i < distance.length; i++) {
               distance[i] = new Array(COL).fill(0);
           }
 
 
           // Vector array to store count of
           // available obstacle eliminations
           let obstacles = new Array(ROW);
           for (let i = 0; i < obstacles.length; i++) {
               obstacles[i] = new Array(COL).fill(-1);
           }
            
           // Push the source cell into queue
           // and use as starting point
           q.push(new pointLoc(source[0], source[1], k));
 
           // Iterate while queue is not empty
           while (q.length > 0) {
 
               let te = q[0];
               let x = te.x;
               let y = te.y;
               let tk = te.k;
 
               // If current cell is same as
               // destination then return distance
               if (x == destination[0]
                   && y == destination[1])
                   return distance[x][y];
 
               q.shift();
 
               // If current cell is an obstacle
               // then decrement current value
               // if possible else skip the cell
               if (matrix[x][y] == 1) {
 
                   if (tk > 0)
                       tk--;
 
                   else
                       continue;
               }
 
               // Cell is skipped only if current
               // value is less than previous
               // value of cell
               if (obstacles[x][y] >= tk)
                   continue;
 
               // Else update value
               obstacles[x][y] = tk;
 
               // Push all valid adjacent
               // cells into queue
               for (let i = 0; i < 4; i++) {
 
                   let ax = x + dir_Row[i];
                   let ay = y + dir_Col[i];
 
                   if (ax < 0 || ay < 0
                       || ax >= ROW || ay >= COL)
                       continue;
 
                   q.push(new pointLoc(ax, ay, tk));
 
                   // Update distance of current
                   // cell from source cell
                   distance[ax][ay] = distance[x][y] + 1;
               }
           }
 
           // If not possible to reach
           // destination from source
           return -1;
       }
 
       // Driver Code
 
       // Given input
       let matrix
           = [[0, 0, 1],
           [1, 0, 1],
           [0, 1, 0]];
 
       let k = 2;
       let source = [0, 0];
       let destination = [2, 2];
       document.write(BFS(matrix, k, source, destination));
 
   // This code is contributed by Potta Lokesh
   </script>

Output

Time Complexity: O(ROW*COL*K)
Auxiliary Space: O(ROW*COL*K)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Shortest path between two points in a Matrix with at most K obstacles

C++

Java

Python3

C#

Javascript

Is MCP Already Outdated? The Real Reason Anthropic Shipped Skills—and How to Pair Them with Milvus

Unlocking 8× Milvus Performance with Cloudian HyperStore and NVIDIA RDMA for S3 Storage

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

LEAVE A REPLY Cancel reply

Most Popular

8 ways I gaslight my AI chatbots to give better answers

I turned Obsidian into the ultimate Android productivity app — here’s how

The Pixel 10 Pro for $524 has my cursor hovering over the ‘buy’ button

I found out if this newcomer can beat the Pixel 10 Pro XL’s camera in a test

EDITOR PICKS

8 ways I gaslight my AI chatbots to give better answers

I turned Obsidian into the ultimate Android productivity app — here’s how

The Pixel 10 Pro for $524 has my cursor hovering over the ‘buy’ button

POPULAR POSTS

8 ways I gaslight my AI chatbots to give better answers

I turned Obsidian into the ultimate Android productivity app — here’s how

The Pixel 10 Pro for $524 has my cursor hovering over the ‘buy’ button

POPULAR CATEGORY

ABOUT US

FOLLOW US