Minimum possible modifications in the matrix to reach destination

0 0 22 minutes read

Given a matrix of size N x M consisting of integers 1, 2, 3 and 4.
Each value represents the possible movement from that cell:

1 -> move left
2 -> move right
3 -> move up
4 -> move down.

The task is to find the minimum possible changes required in the matrix such that there exists a path from (0, 0) to (N-1, M-1).

Examples:

Input : mat[][] = {{2, 2, 4},
{1, 1, 1},
{3, 3, 2}};
Output : 1
Change the value of mat[1][2] to 4. So the sequence of moves will be
(0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2)

Input : mat[][] = {{2, 2, 1},
{4, 2, 3},
{4, 3, 2}}
Output : 2

Prerequisites:
1. Dijkstra’s Algorithm
2.0-1 BFS

Method 1

Let’s consider each cell of the 2D matrix as a node of the weighted graph and each node can has at most four connected nodes(possible four directions). Each edge is weighted as:
- weight(U, V) = 0, if the direction of movement of node U points to V, else
- weight(U, V) = 1
Now, this basically reduces to shortest path problem which can be computed using Dijkstra’s Algorithm

Below is the implementation of the above approach:

C++

// CPP program to find minimum possible
// changes required in the matrix
#include <bits/stdc++.h>
using namespace std;
 
// Function to find next possible node
int nextNode(int x, int y, int dir, int N, int M)
{
    if (dir == 1)
        y--;
    else if (dir == 2)
        y++;
    else if (dir == 3)
        x--;
    else
        x++;
 
    // If node is out of matrix
    if (!(x >= 0 && x < N && y >= 0 && y < M))
        return -1;
    else
        return (x * N + y);
}
 
// Prints shortest paths from src
// to all other vertices
int dijkstra(vector<pair<int, int> >* adj,
             int src, int dest, int N, int M)
{
    // Create a set to store vertices
    // that are being preprocessed
    set<pair<int, int> > setds;
 
    // Create a vector for distances
    // and initialize all distances
    // as infinite (large value)
    vector<int> dist(N * M, INT_MAX);
 
    // Insert source itself in Set
    // and initialize its distance as 0
    setds.insert(make_pair(0, src));
    dist[src] = 0;
 
    /* Looping till all shortest 
        distance are finalized 
        then setds will become empty */
    while (!setds.empty()) {
        // The first vertex in Set
        // is the minimum distance
        // vertex, extract it from set.
        pair<int, int> tmp = *(setds.begin());
        setds.erase(setds.begin());
 
        // vertex label is stored in second
        // of pair (it has to be done this
        // way to keep the vertices sorted
        // distance (distance must be
        // first item in pair)
        int u = tmp.second;
 
        // 'i' is used to get all adjacent
        // vertices of a vertex
        vector<pair<int, int> >::iterator i;
        for (i = adj[u].begin();
             i != adj[u].end(); ++i) {
            // Get vertex label and weight
            // of current adjacent of u.
            int v = (*i).first;
            int weight = (*i).second;
 
            // If there is shorter path from u to v
            if (dist[v] > dist[u] + weight) {
                // If distance of v is not
                // INF then it must be
                // in our set, so removing it
                // and inserting again with
                // updated less distance.
                // Note : We extract only
                // those vertices from Set
                // for which distance is
                // finalized. So for them,
                // we would never reach here
                if (dist[v] != INT_MAX)
                    setds.erase(setds.find(
                        { dist[v], v }));
 
                // Updating distance of v
                dist[v] = dist[u] + weight;
                setds.insert(make_pair(dist[v], v));
            }
        }
    }
 
    // Return the distance
    return dist[dest];
}
 
// Function to find minimum possible
// changes required in the matrix
int MinModifications(vector<vector<int> >& mat)
{
    int N = mat.size(), M = mat[0].size();
 
    // Converting given matrix to a graph
    vector<pair<int, int> > adj[N * M];
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            // Each cell is a node,
            // with label i*N + j
            for (int dir = 1; dir <= 4; dir++) {
                // Label of node if we
                // move in direction dir
                int nextNodeLabel
                    = nextNode(i, j, dir, N, M);
 
                // If invalid(out of matrix)
                if (nextNodeLabel == -1)
                    continue;
 
                // If direction is same as mat[i][j]
                if (dir == mat[i][j])
                    adj[i * N + j].push_back(
                        { nextNodeLabel, 0 });
                else
                    adj[i * N + j].push_back(
                        { nextNodeLabel, 1 });
            }
        }
    }
 
    // Applying dijkstra's algorithm
    return dijkstra(adj, 0,
                    (N - 1) * N + M - 1, N, M);
}
 
// Driver code
int main()
{
    vector<vector<int> > mat = { { 2, 2, 1 },
                                 { 4, 2, 3 },
                                 { 4, 3, 2 } };
 
    // Function call
    cout << MinModifications(mat);
 
    return 0;
}

Java

// Java Code
import java.util.*;
import javafx.util.Pair;
 
public class Main {
 
  // Function to find next possible node
  static int nextNode(int x, int y, int dir, int N, int M)
  {
    if (dir == 1)
      y--;
    else if (dir == 2)
      y++;
    else if (dir == 3)
      x--;
    else
      x++;
 
    // If node is out of matrix
    if (!(x >= 0 && x < N && y >= 0 && y < M))
      return -1;
    else
      return (x * N + y);
  }
 
  // Prints shortest paths from src
  // to all other vertices
  static int dijkstra(List<Pair<Integer, Integer> >[] adj,
                      int src, int dest, int N, int M)
  {
    // Create a set to store vertices
    // that are being preprocessed
    Set<Pair<Integer, Integer> > setds
      = new HashSet<>();
 
    // Create a vector for distances
    // and initialize all distances
    // as infinite (large value)
    int[] dist = new int[N * M];
    Arrays.fill(dist, Integer.MAX_VALUE);
 
    // Insert source itself in Set
    // and initialize its distance as 0
    setds.add(new Pair<>(0, src));
    dist[src] = 0;
 
    /* Looping till all shortest
            distance are finalized
            then setds will become empty */
    while (!setds.isEmpty()) {
      // The first vertex in Set
      // is the minimum distance
      // vertex, extract it from set.
      Iterator<Pair<Integer, Integer> > itr
        = setds.iterator();
      Pair<Integer, Integer> tmp = itr.next();
      setds.remove(tmp);
 
      // vertex label is stored in second
      // of pair (it has to be done this
      // way to keep the vertices sorted
      // distance (distance must be
      // first item in pair)
      int u = tmp.getValue();
 
      // 'i' is used to get all adjacent
      // vertices of a vertex
      Iterator<Pair<Integer, Integer> > itr2
        = adj[u].iterator();
      while (itr2.hasNext()) {
        // Get vertex label and weight
        // of current adjacent of u.
        Pair<Integer, Integer> p = itr2.next();
        int v = p.getKey();
        int weight = p.getValue();
 
        // If there is shorter path from u to v
        if (dist[v] > dist[u] + weight) {
          // If distance of v is not
          // INF then it must be
          // in our set, so removing it
          // and inserting again with
          // updated less distance.
          // Note : We extract only
          // those vertices from Set
          // for which distance is
          // finalized. So for them,
          // we would never reach here
          if (dist[v] != Integer.MAX_VALUE)
            setds.remove(
            new Pair<>(dist[v], v));
 
          // Updating distance of v
          dist[v] = dist[u] + weight;
          setds.add(new Pair<>(dist[v], v));
        }
      }
    }
 
    // Return the distance
    return dist[dest];
  }
 
  // Function to find minimum possible
  // changes required in the matrix
  static int MinModifications(int[][] mat)
  {
    int N = mat.length, M = mat[0].length;
 
    // Converting given matrix to a graph
    List<Pair<Integer, Integer> >[] adj
      = new LinkedList[N * M];
    for (int i = 0; i < N * M; i++)
      adj[i] = new LinkedList<>();
 
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        // Each cell is a node,
        // with label i*N + j
        for (int dir = 1; dir <= 4; dir++) {
          // Label of node if we
          // move in direction dir
          int nextNodeLabel
            = nextNode(i, j, dir, N, M);
 
          // If invalid(out of matrix)
          if (nextNodeLabel == -1)
            continue;
 
          // If direction is same as mat[i][j]
          if (dir == mat[i][j])
            adj[i * N + j].add(
            new Pair<>(nextNodeLabel, 0));
          else
            adj[i * N + j].add(
            new Pair<>(nextNodeLabel, 1));
        }
      }
    }
 
    // Applying dijkstra's algorithm
    return dijkstra(adj, 0, (N - 1) * N + M - 1, N, M);
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int[][] mat
      = { { 2, 2, 1 }, { 4, 2, 3 }, { 4, 3, 2 } };
 
    // Function call
    System.out.println(MinModifications(mat));
  }
}
 
// This code is contributed by ishankhandelwals.

Python3

# Python 3 program to find minimum possible
# changes required in the matrix
import heapq as hq
 
# Function to find next possible node
def nextNode(x, y, dirn, N, M):
    if (dirn == 1):
        y-=1
    elif (dirn == 2):
        y+=1
    elif (dirn == 3):
        x-=1
    else:
        x+=1
 
    # If node is out of matrix
    if (not(x >= 0 and x < N and y >= 0 and y < M)):
        return -1
    else:
        return (x * N + y)
 
 
# Prints shortest paths from src
# to all other vertices
def dijkstra( adj, src, dest, N, M):
    # Create a set to store vertices
    # that are being preprocessed
    setds=[]
 
    # Create a vector for distances
    # and initialize all distances
    # as infinite (large value)
    dist=[float('inf')]*(N * M)
 
    # Insert source itself in Set
    # and initialize its distance as 0
    hq.heappush(setds,(0, src))
    dist[src] = 0
 
    # Looping till all shortest 
    # distance are finalized 
    # then setds will become empty 
    while (setds) :
        # The first vertex in Set
        # is the minimum distance
        # vertex, extract it from set.
        tmp = hq.heappop(setds)
 
        # vertex label is stored in second
        # of pair (it has to be done this
        # way to keep the vertices sorted
        # distance (distance must be
        # first item in pair)
        u = tmp[1]
 
        # 'i' is used to get all adjacent
        # vertices of a vertex
        for i in adj[u] :
            # Get vertex label and weight
            # of current adjacent of u.
 
            v = i[0]
            weight = i[1]
 
            # If there is shorter path from u to v
            if (dist[v] > dist[u] + weight):
                # Updating distance of v
                dist[v] = dist[u] + weight
                hq.heappush(setds, (dist[v], v))
             
         
     
 
    # Return the distance
    return dist[dest]
 
 
# Function to find minimum possible
# changes required in the matrix
def MinModifications(mat):
    N = len(mat); M = len(mat[0])
 
    # Converting given matrix to a graph
    adj=[[] for _ in range(N*M)]
 
    for i in range(N):
        for j in range(M) :
            # Each cell is a node,
            # with label i*N + j
            for dirn in range(1, 5):
                # Label of node if we
                # move in direction dirn
                nextNodeLabel= nextNode(i, j, dirn, N, M)
 
                # If invalid(out of matrix)
                if (nextNodeLabel == -1):
                    continue
 
                # If direction is same as mat[i][j]
                if (dirn == mat[i][j]):
                    adj[i * N + j].append((nextNodeLabel, 0))
                else:
                    adj[i * N + j].append((nextNodeLabel, 1 ))
             
         
     
 
    # Applying dijkstra's algorithm
    return dijkstra(adj, 0,
                    (N - 1) * N + M - 1, N, M)
 
 
# Driver code
if __name__ == '__main__':
    mat = [[2, 2, 1 ,],
        [4, 2, 3 ,],
        [4, 3, 2]]  
 
    # Function call
    print(MinModifications(mat))

C#

// C# program to find minimum possible
// changes required in the matrix
 
using System;
using System.Collections.Generic;
using System.Linq;
 
class Program {
 
    // Function to find next possible node
    static int nextNode(int x, int y, int dir, int N, int M)
    {
        if (dir == 1)
            y--;
        else if (dir == 2)
            y++;
        else if (dir == 3)
            x--;
        else
            x++;
        // If node is out of matrix
        if (!(x >= 0 && x < N && y >= 0 && y < M))
            return -1;
        else
            return (x * N + y);
    }
    // Prints shortest paths from src
    // to all other vertices
    static int dijkstra(List<Tuple<int, int> >[] adj,
                        int src, int dest, int N, int M)
    {
        // Create a set to store vertices
        // that are being preprocessed
        HashSet<Tuple<int, int> > setds
            = new HashSet<Tuple<int, int> >();
        // Create a vector for distances
        // and initialize all distances
        // as infinite (large value)
        int[] dist = new int[N * M];
        for (int i = 0; i < dist.Length; i++)
            dist[i] = int.MaxValue;
        // Insert source itself in Set
        // and initialize its distance as 0
        setds.Add(new Tuple<int, int>(0, src));
        dist[src] = 0;
        /* Looping till all shortest
             distance are finalized
             then setds will become empty */
        while (setds.Count > 0) {
            // The first vertex in Set
            // is the minimum distance
            // vertex, extract it from set.
            Tuple<int, int> tmp = setds.First();
            setds.Remove(tmp);
            // vertex label is stored in second
            // of pair (it has to be done this
            // way to keep the vertices sorted
            // distance (distance must be
            // first item in pair)
            int u = tmp.Item2;
 
            // 'i' is used to get all adjacent
            // vertices of a vertex
            foreach(Tuple<int, int> p in adj[u])
            {
                int v = p.Item1;
                int weight = p.Item2;
                // If distance of v is not
                // INF then it must be
                // in our set, so removing it
                // and inserting again with
                // updated less distance.
                // Note : We extract only
                // those vertices from Set
                // for which distance is
                // finalized. So for them,
                // we would never reach here
                if (dist[v] > dist[u] + weight) {
                    if (dist[v] != int.MaxValue)
                        setds.Remove(new Tuple<int, int>(
                            dist[v], v));
                    // Updating distance of v
                    dist[v] = dist[u] + weight;
                    setds.Add(
                        new Tuple<int, int>(dist[v], v));
                }
            }
        }
 
        return dist[dest];
    }
 
    // Function to find minimum possible
    // changes required in the matrix
    static int MinModifications(int[][] mat)
    {
        int N = mat.Length, M = mat[0].Length;
        // Converting given matrix to a graph
        List<Tuple<int, int> >[] adj
            = new List<Tuple<int, int> >[ N * M ];
        for (int i = 0; i < adj.Length; i++)
            adj[i] = new List<Tuple<int, int> >();
 
        for (int i = 0; i < N; i++) {
 
            for (int j = 0; j < M; j++) {
                // Each cell is a node,
                // with label i*N + j
                for (int dir = 1; dir <= 4; dir++) {
                    // Label of node if we
                    // move in direction dir
                    int nextNodeLabel
                        = nextNode(i, j, dir, N, M);
                    // If invalid(out of matrix)
                    if (nextNodeLabel == -1)
                        continue;
                    // If direction is same as mat[i][j]
                    if (dir == mat[i][j])
                        adj[i * N + j].Add(
                            new Tuple<int, int>(
                                nextNodeLabel, 0));
                    else
                        adj[i * N + j].Add(
                            new Tuple<int, int>(
                                nextNodeLabel, 1));
                }
            }
        }
        // Applying dijkstra's algorithm
        return dijkstra(adj, 0, (N - 1) * N + M - 1, N, M);
    }
    // Driver code
    static void Main(string[] args)
    {
        int[][] mat = new int[][] { new int[] { 2, 2, 1 },
                                    new int[] { 4, 2, 3 },
                                    new int[] { 4, 3, 2 } };
 
        // Function call
        Console.WriteLine(MinModifications(mat));
    }
}

Javascript

// JS code
class Pair{
 constructor(x,y){
     this.first = x;
    this.second=y;
}
}
 
// Function to find next possible node
function nextNode(x, y, dir, N, M) {
    if (dir == 1)
        y--;
    else if (dir == 2)
        y++;
    else if (dir == 3)
        x--;
    else
        x++;
 
    // If node is out of matrix
    if (!(x >= 0 && x < N && y >= 0 && y < M))
        return -1;
    else
        return (x * N + y);
}
 
// Prints shortest paths from src
// to all other vertices
function dijkstra(adj, src, dest, N, M) {
    // Create a set to store vertices
    // that are being preprocessed
    let setds = new Set();
 
    // Create a vector for distances
    // and initialize all distances
    // as infinite (large value)
    let dist = new Array(N * M).fill(Number.MAX_VALUE);
 
    // Insert source itself in Set
    // and initialize its distance as 0
    setds.add(new Pair(0, src));
    dist[src] = 0;
 
    /* Looping till all shortest 
        distance are finalized 
        then setds will become empty */
    while (setds.size > 0) {
        // The first vertex in Set
        // is the minimum distance
        // vertex, extract it from set.
        let tmp = setds.values().next().value;
        setds.delete(setds.values().next().value);
 
        // vertex label is stored in second
        // of pair (it has to be done this
        // way to keep the vertices sorted
        // distance (distance must be
        // first item in pair)
        let u = tmp.second;
 
        // 'i' is used to get all adjacent
        // vertices of a vertex
        for (let i = 0; i < adj[u].length; i++) {
            // Get vertex label and weight
            // of current adjacent of u.
            let v = adj[u][i].first;
            let weight = adj[u][i].second;
 
            // If there is shorter path from u to v
            if (dist[v] > dist[u] + weight) {
                // If distance of v is not
                // INF then it must be
                // in our set, so removing it
                // and inserting again with
                // updated less distance.
                // Note : We extract only
                // those vertices from Set
                // for which distance is
                // finalized. So for them,
                // we would never reach here
                if (dist[v] != Number.MAX_VALUE)
                    setds.delete(new Pair(dist[v], v));
 
                // Updating distance of v
                dist[v] = dist[u] + weight;
                setds.add(new Pair(dist[v], v));
            }
        }
    }
 
    // Return the distance
    return dist[dest];
}
 
// Function to find minimum possible
// changes required in the matrix
function MinModifications(mat) {
    let N = mat.length, M = mat[0].length;
 
    // Converting given matrix to a graph
    let adj = new Array(N * M).fill(null).map(() => []);
 
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            // Each cell is a node,
            // with label i*N + j
            for (let dir = 1; dir <= 4; dir++) {
                // Label of node if we
                // move in direction dir
                let nextNodeLabel
                    = nextNode(i, j, dir, N, M);
 
                // If invalid(out of matrix)
                if (nextNodeLabel == -1)
                    continue;
 
                // If direction is same as mat[i][j]
                if (dir == mat[i][j])
                    adj[i * N + j].push(
                        new Pair(nextNodeLabel, 0));
                else
                    adj[i * N + j].push(
                        new Pair(nextNodeLabel, 1));
            }
        }
    }
 
    // Applying dijkstra's algorithm
    return dijkstra(adj, 0,
                    (N - 1) * N + M - 1, N, M);
}
 
// Driver code
let mat = [
    [2, 2, 1],
    [4, 2, 3],
    [4, 3, 2]
];
 
// Function call
console.log(MinModifications(mat));
 
// This code is contributed by ishankhandelwals.

Output:

Time Complexity : $O(N * M * log(N * M))$

Method 2
Here, edge weights are 0, and 1 only i.e it’s a 0-1 graph. The shortest path in such graphs can be found using 0-1 BFS.

Below is the implementation of the above approach:

C++

// C++ program to find minimum
// possible changes required
// in the matrix
#include <bits/stdc++.h>
using namespace std;
 
// Function to find next possible node
int nextNode(int x, int y, int dir,
             int N, int M)
{
    if (dir == 1)
        y--;
    else if (dir == 2)
        y++;
    else if (dir == 3)
        x--;
    else
        x++;
 
    // If node is out of matrix
    if (!(x >= 0 && x < N && y >= 0 && y < M))
        return -1;
    else
        return (x * N + y);
}
 
// Prints shortest distance
// from given source to
// every other vertex
int zeroOneBFS(vector<pair<int, int> >* adj,
               int src, int dest, int N, int M)
{
    // Initialize distances
    // from given source
    int dist[N * M];
    for (int i = 0; i < N * M; i++)
        dist[i] = INT_MAX;
 
    // Double ended queue to do BFS.
    deque<int> Q;
    dist[src] = 0;
    Q.push_back(src);
 
    while (!Q.empty()) {
        int v = Q.front();
        Q.pop_front();
 
        for (auto i : adj[v]) {
            // Checking for the optimal distance
            if (dist[i.first] > dist[v]
                                    + i.second) {
                dist[i.first] = dist[v]
                                + i.second;
 
                // Put 0 weight edges to front
                // and 1 weight edges to back
                // so that vertices are processed
                // in increasing order of weights.
                if (i.second == 0)
                    Q.push_front(i.first);
                else
                    Q.push_back(i.first);
            }
        }
    }
 
    // Shortest distance to
    // reach destination
    return dist[dest];
}
 
// Function to find minimum possible
// changes required in the matrix
int MinModifications(vector<vector<int> >& mat)
{
    int N = mat.size(), M = mat[0].size();
 
    // Converting given matrix to a graph
    vector<pair<int, int> > adj[N * M];
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            // Each cell is a node
            // with label i*N + j
            for (int dir = 1; dir <= 4; dir++) {
                // Label of node if we
                // move in direction dir
                int nextNodeLabel = nextNode(i, j,
                                             dir, N, M);
 
                // If invalid(out of matrix)
                if (nextNodeLabel == -1)
                    continue;
 
                // If direction is same as mat[i][j]
                if (dir == mat[i][j])
                    adj[i * N + j].push_back(
                        { nextNodeLabel, 0 });
                else
                    adj[i * N + j].push_back(
                        { nextNodeLabel, 1 });
            }
        }
    }
 
    // Applying dijkstra's algorithm
    return zeroOneBFS(adj, 0,
                      (N - 1) * N + M - 1, N, M);
}
 
// Driver code
int main()
{
    vector<vector<int> > mat = { { 2, 2, 1 },
                                 { 4, 2, 3 },
                                 { 4, 3, 2 } };
 
    // Function call
    cout << MinModifications(mat);
 
    return 0;
}

Java

// Java Code
import java.util.*;
import javafx.util.Pair;
 
public class Main {
 
  // Function to find next possible node
  static int nextNode(int x, int y, int dir, int N, int M)
  {
    if (dir == 1)
      y--;
    else if (dir == 2)
      y++;
    else if (dir == 3)
      x--;
    else
      x++;
 
    // If node is out of matrix
    if (!(x >= 0 && x < N && y >= 0 && y < M))
      return -1;
    else
      return (x * N + y);
  }
 
  // Prints shortest paths from src
  // to all other vertices
  static int dijkstra(List<Pair<Integer, Integer> >[] adj,
 
                      int src, int dest, int N, int M)
 
  {
 
    // Create a set to store vertices
    // that are being preprocessed
    Set<Pair<Integer, Integer> > setds
      = new HashSet<>();
    // Create a vector for distances
    // and initialize all distances
    // as infinite (large value)
    int[] dist = new int[N * M];
    Arrays.fill(dist, Integer.MAX_VALUE);
 
    // Insert source itself in Set
    // and initialize its distance as 0
    setds.add(new Pair<>(0, src));
    dist[src] = 0;
 
    /* Looping till all shortest
                distance are finalized
                then setds will become empty */
    while (!setds.isEmpty()) 
    {
       
      // The first vertex in Set
      // is the minimum distance
      // vertex, extract it from set.
      Iterator<Pair<Integer, Integer> > itr
 
        = setds.iterator();
 
      Pair<Integer, Integer> tmp = itr.next();
      setds.remove(tmp);
 
      // vertex label is stored in second
      // of pair (it has to be done this
      // way to keep the vertices sorted
      // distance (distance must be
      // first item in pair)
      int u = tmp.getValue();
 
      // 'i' is used to get all adjacent
      // vertices of a vertex
      Iterator<Pair<Integer, Integer> > itr2
        = adj[u].iterator();
 
      while (itr2.hasNext()) {
 
        // Get vertex label and weight
        // of current adjacent of u.
        Pair<Integer, Integer> p = itr2.next();
        int v = p.getKey();
        int weight = p.getValue();
 
        // If there is shorter path from u to v
        if (dist[v] > dist[u] + weight)
        {
 
          // If distance of v is not
          // INF then it must be
          // in our set, so removing it
          // and inserting again with
          // updated less distance.
          // Note : We extract only
          // those vertices from Set
          // for which distance is
          // finalized. So for them,
          // we would never reach here
          if (dist[v] != Integer.MAX_VALUE)
 
            setds.remove(new Pair<>(dist[v], v));
 
          // Updating distance of v
          dist[v] = dist[u] + weight;
          setds.add(new Pair<>(dist[v], v));
        }
      }
    }
 
    // Return the distance
    return dist[dest];
  }
 
  // Function to find minimum possible
  // changes required in the matrix
  static int MinModifications(int[][] mat)
  {
 
    int N = mat.length, M = mat[0].length;
 
    // Converting given matrix to a graph
    List<Pair<Integer, Integer> >[] adj
 
      = new LinkedList[N * M];
 
    for (int i = 0; i < N * M; i++)
      adj[i] = new LinkedList<>();
 
    for (int i = 0; i < N; i++) 
    {
      for (int j = 0; j < M; j++)
      {
 
        // Each cell is a node,
        // with label i*N + j
        for (int dir = 1; dir <= 4; dir++) 
        {
 
          // Label of node if we
          // move in direction dir
          int nextNodeLabel = nextNode(i, j, dir, N, M);
 
          // If invalid(out of matrix)
          if (nextNodeLabel == -1)
            continue;
 
          // If direction is same as mat[i][j]
          if (dir == mat[i][j])
            adj[i * N + j].add(
            new Pair<>(nextNodeLabel, 0));
          else
            adj[i * N + j].add(
            new Pair<>(nextNodeLabel, 1));
        }
      }
    }
 
    // Applying dijkstra's algorithm
    return dijkstra(adj, 0, (N - 1) * N + M - 1, N, M);
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    int[][] mat
      = { { 2, 2, 1 }, { 4, 2, 3 }, { 4, 3, 2 } };
 
    // Function call
    System.out.println(MinModifications(mat));
  }
}
 
// This code is contributed by ishankhandelwals.

Python3

# Python3 program to find minimum
# possible changes required
# in the matrix
from collections import deque
 
# Function to find next possible node
def nextNode(x, y, dir, N, M):
    if (dir == 1):
        y -= 1
    elif (dir == 2):
        y += 1
    elif (dir == 3):
        x -= 1
    else:
        x += 1
 
    # If node is out of matrix
    if (not (x >= 0 and x < N and y >= 0 and y < M)):
        return -1
    else:
        return (x * N + y)
 
# Prints shortest distance
# from given source to
# every other vertex
def zeroOneBFS(adj, src, dest, N, M):
   
    # Initialize distances
    # from given source
    dist = [10**8] *(N * M)
 
    # Double ended queue to do BFS.
    Q = deque()
    dist[src] = 0
    Q.append(src)
 
    while (len(Q) > 0):
        v = Q.popleft()
 
        for i in adj[v]:
           
            # print(i)
            # Checking for the optimal distance
            if (dist[i[0]] > dist[v] + i[1]):
                dist[i[0]] = dist[v] + i[1]
                 
                # Put 0 weight edges to front
                # and 1 weight edges to back
                # so that vertices are processed
                # in increasing order of weights.
                if (i[1] == 0):
                    Q.appendleft(i[0])
                else:
                    Q.append(i[0])
 
    # Shortest distance to
    # reach destination
    return dist[dest]
 
# Function to find minimum possible
# changes required in the matrix
def MinModifications(mat):
    N, M = len(mat), len(mat[0])
 
    # Converting given matrix to a graph
    adj = [[] for i in range(N * M)]
 
    for i in range(N):
        for j in range(M):
           
            # Each cell is a node
            # with label i*N + j
            for dir in range(1, 5):
               
                # Label of node if we
                # move in direction dir
                nextNodeLabel = nextNode(i, j, dir, N, M)
 
                # If invalid(out of matrix)
                if (nextNodeLabel == -1):
                    continue
 
                # If direction is same as mat[i][j]
                if (dir == mat[i][j]):
                    adj[i * N + j].append([nextNodeLabel, 0])
                else:
                    adj[i * N + j].append([nextNodeLabel, 1])
 
    # Applying dijkstra's algorithm
    return zeroOneBFS(adj, 0, (N - 1) * N + M - 1, N, M)
 
# Driver code
if __name__ == '__main__':
    mat = [ [ 2, 2, 1 ],
             [ 4, 2, 3 ],
             [ 4, 3, 2 ] ]
 
    # Function call
    print (MinModifications(mat))
 
# This code is contributed by mohit kumar 29.

C#

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
 
// C# program to find minimum
// possible changes required
// in the matrix
 
 
class HelloWorld {
  
     
    // Function to find next possible node
    public static int nextNode(int x, int y, int dir, int N, int M)
    {
        if (dir == 1)
            y--;
        else if (dir == 2)
            y++;
        else if (dir == 3)
            x--;
        else
            x++;
 
        // If node is out of matrix
        if (!(x >= 0 && x < N && y >= 0 && y < M))
            return -1;
        else
            return (x * N + y);
    }
 
    // Prints shortest distance
    // from given source to
    // every other vertex
    public static int zeroOneBFS(List<List<KeyValuePair<int,int>>> adj, int src, int dest, int N, int M)
    {
        // Initialize distances
        // from given source
        int[] dist = new int[N*M];
        for (int i = 0; i < N * M; i++)
            dist[i] = 2147483647;
 
        // Double ended queue to do BFS.
        List<int> Q = new List<int>();
        dist[src] = 0;
        Q.Add(src);
 
        while (Q.Count > 0) {
            int v = Q[0];
            Q.RemoveAt(0);
 
            foreach(var i in adj[v]){
                // Checking for the optimal distance
                if (dist[i.Key] > dist[v] + i.Value) {
                    dist[i.Key] = dist[v] + i.Value;
 
                    // Put 0 weight edges to front
                    // and 1 weight edges to back
                    // so that vertices are processed
                    // in increasing order of weights.
                    if (i.Value == 0)
                        Q.Insert(0, i.Key);
                    else
                        Q.Add(i.Key);
                }
            }
        }
 
        // Shortest distance to
        // reach destination
        return dist[dest];
    }
     
    // Function to find minimum possible
    // changes required in the matrix
    public static int MinModifications(int[][] mat)
    {
        int N = mat.Length;
        int M = mat[0].Length;
 
        // Converting given matrix to a graph
        List<List<KeyValuePair<int,int>>> adj = new List<List<KeyValuePair<int,int>>>();
        for(int i = 0; i < N*M; i++){
            adj.Add(new List<KeyValuePair<int,int>>());
        }
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // Each cell is a node
                // with label i*N + j
                for (int dir = 1; dir <= 4; dir++) {
                    // Label of node if we
                    // move in direction dir
                    int nextNodeLabel = nextNode(i, j, dir, N, M);
 
                    // If invalid(out of matrix)
                    if (nextNodeLabel == -1)
                        continue;
 
                    // If direction is same as mat[i][j]
                    if (dir == mat[i][j]) 
                        adj[i * N + j].Add(new KeyValuePair<int,int>(nextNodeLabel, 0));
                    else
                        adj[i * N + j].Add(new KeyValuePair<int,int>(nextNodeLabel, 1));
                }
            }
        }
 
        // Applying dijkstra's algorithm
        return zeroOneBFS(adj, 0, (N - 1) * N + M - 1, N, M);
    }
     
    // Driver code. 
    static void Main() {
 
        int[][] mat = { new int[] { 2, 2, 1 },
                         new int[] { 4, 2, 3 },
                         new int[] { 4, 3, 2 } };
 
        // Function call
        Console.WriteLine(MinModifications(mat));  
    }
}
 
// The code is contributed by Arushi Jindal.

Javascript

<script>
 
// Javascript program to find minimum
// possible changes required in the matrix
 
// Function to find next possible node
function nextNode(x, y, dir, N, M)
{
    if (dir == 1)
        y--;
    else if (dir == 2)
        y++;
    else if (dir == 3)
        x--;
    else
        x++;
  
    // If node is out of matrix
    if (!(x >= 0 && x < N && y >= 0 && y < M))
        return -1;
    else
        return (x * N + y);
}
 
// Prints shortest distance
// from given source to
// every other vertex
function zeroOneBFS(adj, src, dest, N, M)
{
     
    // Initialize distances
    // from given source
    let dist = new Array(N * M);
    for(let i = 0; i < N * M; i++)
        dist[i] = Number.MAX_VALUE;
  
    // Double ended queue to do BFS.
    let Q = [];
    dist[src] = 0;
    Q.push(src);
  
    while (Q.length != 0) 
    {
        let v = Q.shift();
  
        for(let i = 0; i < adj[v].length; i++)
        {
             
            // Checking for the optimal distance
            if (dist[adj[v][i][0]] > dist[v] + 
                     adj[v][i][1])
            {
                dist[adj[v][i][0]] = dist[v] + 
                                      adj[v][i][1];
  
                // Put 0 weight edges to front
                // and 1 weight edges to back
                // so that vertices are processed
                // in increasing order of weights.
                if (adj[v][i][1] == 0)
                    Q.push(adj[v][i][0]);
                else
                    Q.push(adj[v][i][0]);
            }
        }
    }
  
    // Shortest distance to
    // reach destination
    return dist[dest];
}
 
// Function to find minimum possible
// changes required in the matrix
function MinModifications(mat)
{
    let N = mat.length, M = mat[0].length;
  
    // Converting given matrix to a graph
    let adj = new Array(N * M);
     for(let i = 0; i < (N * M); i++)
    {
        adj[i] = [];
    }
     
    for(let i = 0; i < N; i++)
    {
        for(let j = 0; j < M; j++)
        {
             
            // Each cell is a node
            // with label i*N + j
            for(let dir = 1; dir <= 4; dir++) 
            {
                 
                // Label of node if we
                // move in direction dir
                let nextNodeLabel = nextNode(i, j,
                                             dir, N, M);
  
                // If invalid(out of matrix)
                if (nextNodeLabel == -1)
                    continue;
  
                // If direction is same as mat[i][j]
                if (dir == mat[i][j])
                    adj[i * N + j].push(
                        [nextNodeLabel, 0]);
                else
                    adj[i * N + j].push(
                        [nextNodeLabel, 1]);
            }
        }
    }
  
    // Applying dijkstra's algorithm
    return zeroOneBFS(adj, 0, (N - 1) * N + M - 1, 
                      N, M);
}
 
// Driver code
let mat = [ [ 2, 2, 1 ], 
            [ 4, 2, 3 ], 
            [ 4, 3, 2 ] ];
             
document.write(MinModifications(mat));
 
// This code is contributed by unknown2108
 
</script>

Output:

Time Complexity : $O(N * M)$
Auxiliary Space: O(N * M)

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 zambiatek!