Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Matrix in Data Structure
2.1.
Initialize a matrix in C++
2.2.
Initialize a matrix in java
3.
Problem Statement
3.1.
Example
3.1.1.
Input 
3.1.2.
Output
3.2.
Explanation
4.
Approach
5.
Algorithm
6.
Implementation in C++
6.1.
Output
7.
Complexities
7.1.
Time Complexity
7.2.
Space complexity
8.
Frequently Asked Questions
8.1.
Can we say that a 2D array and Matrix are the same?
8.2.
Are vectors and arrays the same?
8.3.
Why are vectors not based on indexes?
8.4.
What are the differences between a 1-D and a 2-D array?
8.5.
Is a NumPy array called a matrix?
9.
Conclusion
Last Updated: Mar 27, 2024
Hard

Pair of positions in matrix which are not accessible

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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

Pair of Positions in Matrix which are not Accessible

Matrix in Data Structure

A matrix is a group of numbers that have been organized in rows and columns. The components of a matrix must be enclosed in parentheses or brackets.appr

Matrix in Data Structure

Initialize a matrix in C++

int integer_Matrix_2d [Row ][Col];

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Problem Statement

Pair of positions in the matrix which are not accessible. 

Suppose X is a positive integer. Consider a 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:-

Problem Statement

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.

Explanation

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);
        }
    }
}

Output

6

Complexities

Time 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. 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.

Check out this article - Balanced Parentheses

Frequently Asked Questions

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.

Conclusion

This post taught us how to get Pair of positions in matrix which are not accessible. Please check some crucial algorithms that will improve your competitive coding abilities and maybe prepare you for your interview.

Check Out these articles mentioned below.

If you face any doubt, please comment, and we will love to answer your questions.

Want expertise in Python for your next web development project? Check out our course.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Determine whether we can travel to every node under the given conditions
Next article
Find palindromic path of given length K in a complete Binary Weighted Graph
Live masterclass