Do you think IIT Guwahati certified course can help you in your career?
Introduction
Hello readers, I Hope you are well. We will go through the understanding of the matrix first and then move into Pair of positions in matrix which are not accessible. In this article, we will discuss Pair of positions in matrix which are not accessible. Before that, we have to understand what a matrix is.
Where Row and Col are the Rows of the matrix and the Columns of the Matrix, respectively.
Initialize a matrix in java
int [ ][ ] integer_Matrix_2d = new int[Row][Col];
Where Row and Col are the Rows of the matrix and the Columns of the Matrix, respectively
Now We move into Pair of positions in the matrix which are not accessible.
Problem Statement
Pair of positions in the matrix which are not accessible.
Suppose X is a positive integer. Consider a X x X matrix. Except for the specified pair of cells (a1, b1), (a2, b2), no other cell can be accessed from another cell. That is, there is a path from (a2, b2) to any other cell (a1, b1). The goal is to determine the number of pairings such that cell (a2, b2) cannot be accessed from pair (a1, b1) (a1, b1).
In simple words, we have to find a number of paths that can be connected to not visited cell. Also, count the reverse order.
Understand this above question with a pictorial representation:-
Example
Input
X = 2
Output
6
Explanation
Acceptable route 1: (1, 1) (1, 2)
Acceptable route 2: (1, 2) (2, 2)
No cell can be accessed from cell (2, 1), and no cell can be accessed from it.
Approach
To get Pair of positions in the matrix which are not accessible, follow this:-
Think of the cells as nodes with numbers ranging from 1 to X*X. Using (a - 1)*X + b, each cell (a, b) may be mapped to a number.
Now, think of every permitted path as an edge connecting two nodes. This will lead to a disjoint set of the linked component.
Now, we may use DFS Algorithm or BFS to quickly identify the number of nodes or size of a linked component, let's say a. The number of inaccessible pathways is now equal to a*(X*X - a).
For each connected path, we may use this method to identify non-accessible pathways.
Algorithm
Mapping the cell coordinate into the node number and inserting the edge between the edges.
Next, we must initialize the number of linked vertices discovered by DFS, beginning from “i” in order to count the non-accessible cells.
Next, make a new function and use DFS to count the linked vertices in a component that contains x.
Stores the sum in the count.
Increasing the associated component's node count.
Implementation in C++
/*To count the number of non accessible pair places in matrices in c++ */
#include <bits/stdc++.h>
using namespace std;
void depth_first_search(vector < int > arr_graph[], bool arr_checked[],
int x, int * sum);
int all_Non_Accessible(vector < int > arr_graph[], int X);
void path_Adding(vector < int > arr_graph[], int X, int x1,
int y1, int x2, int y2);
/* Main Program*/
int main() {
int X = 2;
vector < int > arr_graph[X * X + 1];
path_Adding(arr_graph, X, 1, 1, 1, 2);
path_Adding(arr_graph, X, 1, 2, 2, 2);
cout << all_Non_Accessible(arr_graph, X) << endl;
return 0;
}
/* Adding an edge between two edges.*/
void path_Adding(vector < int > arr_graph[], int X, int x1,
int y1, int x2, int y2) {
/*Converting a cell's location to a node's number.*/
int a = (x1 - 1) * X + y1;
int b = (x2 - 1) * X + y2;
/* Putting in the edge.*/
arr_graph[a].push_back(b);
arr_graph[b].push_back(a);
}
/* Return the total number of inaccessible cells.*/
int all_Non_Accessible(vector < int > arr_graph[], int X) {
bool arr_checked[X * X + X];
memset(arr_checked, false, sizeof(arr_checked));
int ans = 0;
for (int i = 1; i <= X * X; i++) {
if (!arr_checked[i]) {
arr_checked[i] = true;
/* Create an initial count of the related vertices located by the depth-first search, starting at i. */
int sum = 1;
depth_first_search(arr_graph, arr_checked, i, & sum);
ans += sum * (X * X - sum);
}
}
return ans;
}
/* In a component containing x, the number of related vertices are counted and maintain the count in sum.*/
void depth_first_search(vector < int > arr_graph[], bool arr_checked[],
int x, int * sum) {
for (int i = 0; i < arr_graph[x].size(); i++) {
if (!arr_checked[arr_graph[x][i]]) {
/* A linked component's node count is being increased. */
( * sum) ++;
arr_checked[arr_graph[x][i]] = true;
depth_first_search(arr_graph, arr_checked, arr_graph[x][i], sum);
}
}
}
You can also try this code with Online C++ Compiler
O(X * X): Where X is the size of the square matrix.
Reason: The nodes in each cell range from 1 to X*X. Using (x - 1)*X + y, each cell (x, y) may be converted to a number. So, X * X is the time complexity.
Space complexity
O(X * X): Where X is the size of the square matrix.
Reason: The nodes in each cell range from 1 to X*X. We have a matrix of X*X. So, X * X is the space complexity.
Can we say that a 2D array and Matrix are the same?
A matrix is a 2D array that adheres to linear algebraic laws. As a result, it is a subset of more generic arrays, which may have greater dimensions or not always adhere to the laws of matrix algebra.
Are vectors and arrays the same?
While arrays may be constructed statically or dynamically with a basic data type interface, vectors are built as dynamic arrays with a list interface. While the size of vectors can increase and decrease since they are allocated on heap memory, the size of arrays is fixed.
Why are vectors not based on indexes?
Because they are dynamic, vectors can change in size as elements are added or removed. It is more time-consuming to access items since it is not index-based and requires the usage of iterators.
What are the differences between a 1-D and a 2-D array?
A one-dimensional array keeps track of a single list of different elements with related data types. An array of different arrays, a list of different lists, or an array of different one-dimensional arrays are all stored in a two-dimensional array. It displays a list of several data objects as a representation.
Is a NumPy array called a matrix?
While NumPy arrays are N-dimensional, NumPy matrices are strictly 2-dimensional. The characteristics and methods of Ndarrays are all passed down to matrix objects since they are a subclass of Ndarray.
85+ registered