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 nodeint 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 verticesint 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 matrixint 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 codeint main(){ vector<vector<int> > mat = { { 2, 2, 1 }, { 4, 2, 3 }, { 4, 3, 2 } }; // Function call cout << MinModifications(mat); return 0;} |
Java
// Java Codeimport 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 matriximport heapq as hq# Function to find next possible nodedef 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 verticesdef 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 matrixdef 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 codeif __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 matrixusing 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 codeclass Pair{ constructor(x,y){ this.first = x; this.second=y;}}// Function to find next possible nodefunction 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 verticesfunction 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 matrixfunction 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 codelet mat = [ [2, 2, 1], [4, 2, 3], [4, 3, 2]];// Function callconsole.log(MinModifications(mat));// This code is contributed by ishankhandelwals. |
Output:
2
Time Complexity : 
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 nodeint 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 vertexint 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 matrixint 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 codeint main(){ vector<vector<int> > mat = { { 2, 2, 1 }, { 4, 2, 3 }, { 4, 3, 2 } }; // Function call cout << MinModifications(mat); return 0;} |
Java
// Java Codeimport 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 matrixfrom collections import deque# Function to find next possible nodedef 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 vertexdef 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 matrixdef 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 codeif __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 matrixclass 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 nodefunction 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 vertexfunction 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 matrixfunction 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 codelet mat = [ [ 2, 2, 1 ], [ 4, 2, 3 ], [ 4, 3, 2 ] ]; document.write(MinModifications(mat));// This code is contributed by unknown2108</script> |
Output:
2
Time Complexity : 
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
