矩阵中不可访问的位置对数-yiteyi-C++库

给定一个正整数 N 考虑矩阵 N×N 除了以（x1，y1），（x2，y2）形式存在的给定对单元，即（x2，y2）到（x1，y1）之间存在路径（可访问），任何其他单元都无法访问。任务是找到配对（a1，b1），（a2，b2）的计数，这样就无法从（a1，b1）访问单元（a2，b2）。 例如：

null

Input : N = 2Allowed path 1: (1, 1) (1, 2)Allowed path 2: (1, 2) (2, 2)Output : 6Cell (2, 1) is not accessible from any celland no cell is accessible from it.

图片[1]-矩阵中不可访问的位置对数-yiteyi-C++库

(1, 1) - (2, 1)(1, 2) - (2, 1)(2, 2) - (2, 1)(2, 1) - (1, 1)(2, 1) - (1, 2)(2, 1) - (2, 2)

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

将每个单元格作为一个节点，编号从1到N*N。每个单元（x，y）可以使用（x – 1）*n+y映射到数字。现在，考虑每个给定的允许路径作为节点之间的边。这将形成一组不相交的连接组件。现在，使用深度优先遍历或宽度优先遍历，我们可以很容易地找到连接组件的节点数或大小，比如x。现在，不可访问路径的计数是x*（N*N–x）。这样，我们可以为每个连接的路径找到不可访问的路径。以下是该方法的实施：

C++

                         // C++ program to count number of pair of positions                       
                         // in matrix which are not accessible                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Counts number of vertices connected in a component                       
                         // containing x. Stores the count in k.                       
                         void                                     dfs(vector<                                     int                                     > graph[],                                     bool                                     visited[],                       
                                                 int                                     x,                                     int                                     *k)                       
                         {                       
                                                 for                                     (                                     int                                     i = 0; i < graph[x].size(); i++)                       
                                                 {                       
                                                 if                                     (!visited[graph[x][i]])                       
                                                 {                       
                                                 // Incrementing the number of node in                       
                                                 // a connected component.                       
                                                 (*k)++;                       
           
                                                 visited[graph[x][i]] =                                     true                                     ;                       
                                                 dfs(graph, visited, graph[x][i], k);                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Return the number of count of non-accessible cells.                       
                         int                                     countNonAccessible(vector<                                     int                                     > graph[],                                     int                                     N)                       
                         {                       
                                                 bool                                     visited[N*N + N];                       
                                                 memset                                     (visited,                                     false                                     ,                                     sizeof                                     (visited));                       
           
                                                 int                                     ans = 0;                       
                                                 for                                     (                                     int                                     i = 1; i <= N*N; i++)                       
                                                 {                       
                                                 if                                     (!visited[i])                       
                                                 {                       
                                                 visited[i] =                                     true                                     ;                       
           
                                                 // Initialize count of connected                       
                                                 // vertices found by DFS starting                       
                                                 // from i.                       
                                                 int                                     k = 1;                       
                                                 dfs(graph, visited, i, &k);                       
           
                                                 // Update result                       
                                                 ans += k * (N*N - k);                       
                                                 }                       
                                                 }                       
                                                 return                                     ans;                       
                         }                       
           
                         // Inserting the edge between edge.                       
                         void                                     insertpath(vector<                                     int                                     > graph[],                                     int                                     N,                                     int                                     x1,                       
                                                 int                                     y1,                                     int                                     x2,                                     int                                     y2)                       
                         {                       
                                                 // Mapping the cell coordinate into node number.                       
                                                 int                                     a = (x1 - 1) * N + y1;                       
                                                 int                                     b = (x2 - 1) * N + y2;                       
           
                                                 // Inserting the edge.                       
                                                 graph[a].push_back(b);                       
                                                 graph[b].push_back(a);                       
                         }                       
           
                         // Driven Program                       
                         int                                     main()                       
                         {                       
                                                 int                                     N = 2;                       
           
                                                 vector<                                     int                                     > graph[N*N + 1];                       
           
                                                 insertpath(graph, N, 1, 1, 1, 2);                       
                                                 insertpath(graph, N, 1, 2, 2, 2);                       
           
                                                 cout << countNonAccessible(graph, N) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count number of                       
                         // pair of positions in matrix                       
                         // which are not accessible                       
                         import                                     java.util.*;                       
                         class                                     GFG                       
                         {                       
           
                         static                                     int                                     k;                       
           
                         // Counts number of vertices connected                       
                         // in a component containing x.                       
                         // Stores the count in k.                       
                         static                                     void                                     dfs(Vector<Integer> graph[],                       
                                                 boolean                                     visited[],                                     int                                     x)                       
                         {                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < graph[x].size(); i++)                       
                                                 {                       
                                                 if                                     (!visited[graph[x].get(i)])                       
                                                 {                       
                                                 // Incrementing the number of node in                       
                                                 // a connected component.                       
                                                 (k)++;                       
           
                                                 visited[graph[x].get(i)] =                                     true                                     ;                       
                                                 dfs(graph, visited, graph[x].get(i));                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Return the number of count of non-accessible cells.                       
                         static                                     int                                     countNonAccessible(Vector<Integer> graph[],                                     int                                     N)                       
                         {                       
                                                 boolean                                     []visited =                                     new                                     boolean                                     [N * N + N];                       
           
                                                 int                                     ans =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= N * N; i++)                       
                                                 {                       
                                                 if                                     (!visited[i])                       
                                                 {                       
                                                 visited[i] =                                     true                                     ;                       
           
                                                 // Initialize count of connected                       
                                                 // vertices found by DFS starting                       
                                                 // from i.                       
                                                 int                                     k =                                     1                                     ;                       
                                                 dfs(graph, visited, i);                       
           
                                                 // Update result                       
                                                 ans += k * (N * N - k);                       
                                                 }                       
                                                 }                       
                                                 return                                     ans;                       
                         }                       
           
                         // Inserting the edge between edge.                       
                         static                                     void                                     insertpath(Vector<Integer> graph[],                       
                                                 int                                     N,                                     int                                     x1,                                     int                                     y1,                       
                                                 int                                     x2,                                     int                                     y2)                       
                         {                       
                                                 // Mapping the cell coordinate into node number.                       
                                                 int                                     a = (x1 -                                     1                                     ) * N + y1;                       
                                                 int                                     b = (x2 -                                     1                                     ) * N + y2;                       
           
                                                 // Inserting the edge.                       
                                                 graph[a].add(b);                       
                                                 graph[b].add(a);                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main(String args[])                       
                         {                       
                                                 int                                     N =                                     2                                     ;                       
           
                                                 Vector[] graph =                                     new                                     Vector[N * N +                                     1                                     ];                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= N * N; i++)                       
                                                 graph[i] =                                     new                                     Vector<Integer>();                       
                                                 insertpath(graph, N,                                     1                                     ,                                     1                                     ,                                     1                                     ,                                     2                                     );                       
                                                 insertpath(graph, N,                                     1                                     ,                                     2                                     ,                                     2                                     ,                                     2                                     );                       
           
                                                 System.out.println(countNonAccessible(graph, N));                       
                         }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

Python3

                         # Python3 program to count number of pair of                       
                         # positions in matrix which are not accessible                       
           
                         # Counts number of vertices connected in a                       
                         # component containing x. Stores the count in k.                       
                         def                                     dfs(graph,visited, x, k):                       
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (graph[x])):                       
                                                 if                                     (                                     not                                     visited[graph[x][i]]):                       
                                   
                                                 # Incrementing the number of node                       
                                                 # in a connected component.                       
                                                 k[                                     0                                     ]                                     +                                     =                                     1                       
           
                                                 visited[graph[x][i]]                                     =                                     True                       
                                                 dfs(graph, visited, graph[x][i], k)                       
           
                         # Return the number of count of                       
                         # non-accessible cells.                       
                         def                                     countNonAccessible(graph, N):                       
                                                 visited                                     =                                     [                                     False                                     ]                                     *                                     (N                                     *                                     N                                     +                                     N)                       
           
                                                 ans                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , N                                     *                                     N                                     +                                     1                                     ):                       
                                                 if                                     (                                     not                                     visited[i]):                       
                                                 visited[i]                                     =                                     True                       
           
                                                 # Initialize count of connected                       
                                                 # vertices found by DFS starting                       
                                                 # from i.                       
                                                 k                                     =                                     [                                     1                                     ]                       
                                                 dfs(graph, visited, i, k)                       
           
                                                 # Update result                       
                                                 ans                                     +                                     =                                     k[                                     0                                     ]                                     *                                     (N                                     *                                     N                                     -                                     k[                                     0                                     ])                       
                                                 return                                     ans                       
           
                         # Inserting the edge between edge.                       
                         def                                     insertpath(graph, N, x1, y1, x2, y2):                       
                                   
                                                 # Mapping the cell coordinate                       
                                                 # into node number.                       
                                                 a                                     =                                     (x1                                     -                                     1                                     )                                     *                                     N                                     +                                     y1                       
                                                 b                                     =                                     (x2                                     -                                     1                                     )                                     *                                     N                                     +                                     y2                       
           
                                                 # Inserting the edge.                       
                                                 graph[a].append(b)                       
                                                 graph[b].append(a)                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
           
                                                 N                                     =                                     2                       
           
                                                 graph                                     =                                     [[]                                     for                                     i                                     in                                     range                                     (N                                     *                                     N                                     +                                     1                                     )]                       
           
                                                 insertpath(graph, N,                                     1                                     ,                                     1                                     ,                                     1                                     ,                                     2                                     )                       
                                                 insertpath(graph, N,                                     1                                     ,                                     2                                     ,                                     2                                     ,                                     2                                     )                       
           
                                                 print                                     (countNonAccessible(graph, N))                       
           
                         # This code is contributed by PranchalK                       

C#

                         // C# program to count number of                       
                         // pair of positions in matrix                       
                         // which are not accessible                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG                       
                         {                       
                         static                                     int                                     k;                       
           
                         // Counts number of vertices connected                       
                         // in a component containing x.                       
                         // Stores the count in k.                       
                         static                                     void                                     dfs(List<                                     int                                     > []graph,                       
                                                 bool                                     []visited,                                     int                                     x)                       
                         {                       
                                                 for                                     (                                     int                                     i = 0; i < graph[x].Count; i++)                       
                                                 {                       
                                                 if                                     (!visited[graph[x][i]])                       
                                                 {                       
                                                 // Incrementing the number of node in                       
                                                 // a connected component.                       
                                                 (k)++;                       
           
                                                 visited[graph[x][i]] =                                     true                                     ;                       
                                                 dfs(graph, visited, graph[x][i]);                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Return the number of count                       
                         // of non-accessible cells.                       
                         static                                     int                                     countNonAccessible(List<                                     int                                     > []graph,                       
                                                 int                                     N)                       
                         {                       
                                                 bool                                     []visited =                                     new                                     bool                                     [N * N + N];                       
           
                                                 int                                     ans = 0;                       
                                                 for                                     (                                     int                                     i = 1; i <= N * N; i++)                       
                                                 {                       
                                                 if                                     (!visited[i])                       
                                                 {                       
                                                 visited[i] =                                     true                                     ;                       
           
                                                 // Initialize count of connected                       
                                                 // vertices found by DFS starting                       
                                                 // from i.                       
                                                 int                                     k = 1;                       
                                                 dfs(graph, visited, i);                       
           
                                                 // Update result                       
                                                 ans += k * (N * N - k);                       
                                                 }                       
                                                 }                       
                                                 return                                     ans;                       
                         }                       
           
                         // Inserting the edge between edge.                       
                         static                                     void                                     insertpath(List<                                     int                                     > []graph,                       
                                                 int                                     N,                                     int                                     x1,                                     int                                     y1,                       
                                                 int                                     x2,                                     int                                     y2)                       
                         {                       
                                                 // Mapping the cell coordinate into node number.                       
                                                 int                                     a = (x1 - 1) * N + y1;                       
                                                 int                                     b = (x2 - 1) * N + y2;                       
           
                                                 // Inserting the edge.                       
                                                 graph[a].Add(b);                       
                                                 graph[b].Add(a);                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main(String []args)                       
                         {                       
                                                 int                                     N = 2;                       
           
                                                 List<                                     int                                     >[] graph =                                     new                                     List<                                     int                                     >[N * N + 1];                       
                                                 for                                     (                                     int                                     i = 1; i <= N * N; i++)                       
                                                 graph[i] =                                     new                                     List<                                     int                                     >();                       
                                                 insertpath(graph, N, 1, 1, 1, 2);                       
                                                 insertpath(graph, N, 1, 2, 2, 2);                       
           
                                                 Console.WriteLine(countNonAccessible(graph, N));                       
                         }                       
                         }                       
           
                         // This code is contributed by PrinciRaj1992                       

Javascript

                         <script>                       
           
                         // JavaScript program to count number of                       
                         // pair of positions in matrix                       
                         // which are not accessible                       
           
                         let k;                       
           
                         // Counts number of vertices connected                       
                         // in a component containing x.                       
                         // Stores the count in k.                       
                         function                                     dfs(graph,visited,x)                       
                         {                       
                                                 for                                     (let i = 0; i < graph[x].length; i++)                       
                                                 {                       
                                                 if                                     (!visited[graph[x][i]])                       
                                                 {                       
                                                 // Incrementing the number of node in                       
                                                 // a connected component.                       
                                                 (k)++;                       
                                   
                                                 visited[graph[x][i]] =                                     true                                     ;                       
                                                 dfs(graph, visited, graph[x][i]);                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Return the number of count of non-accessible cells.                       
                         function                                     countNonAccessible(graph,N)                       
                         {                       
                                                 let visited =                                     new                                     Array(N * N + N);                       
                                   
                                                 let ans = 0;                       
                                                 for                                     (let i = 1; i <= N * N; i++)                       
                                                 {                       
                                                 if                                     (!visited[i])                       
                                                 {                       
                                                 visited[i] =                                     true                                     ;                       
                                   
                                                 // Initialize count of connected                       
                                                 // vertices found by DFS starting                       
                                                 // from i.                       
                                                 let k = 1;                       
                                                 dfs(graph, visited, i);                       
                                   
                                                 // Update result                       
                                                 ans += k * (N * N - k);                       
                                                 }                       
                                                 }                       
                                                 return                                     ans;                       
                         }                       
           
                         // Inserting the edge between edge.                       
                         function                                     insertpath(graph,N,x1,y1,x2,y2)                       
                         {                       
                                                 // Mapping the cell coordinate into node number.                       
                                                 let a = (x1 - 1) * N + y1;                       
                                                 let b = (x2 - 1) * N + y2;                       
                                   
                                                 // Inserting the edge.                       
                                                 graph[a].push(b);                       
                                                 graph[b].push(a);                       
                         }                       
           
                         // Driver Code                       
                         let N = 2;                       
                                   
                         let graph =                                     new                                     Array(N * N + 1);                       
                         for                                     (let i = 1; i <= N * N; i++)                       
                                                 graph[i] = [];                       
                         insertpath(graph, N, 1, 1, 1, 2);                       
                         insertpath(graph, N, 1, 2, 2, 2);                       
           
                         document.write(countNonAccessible(graph, N));                       
           
           
                         // This code is contributed by rag2127                       
           
                         </script>                       

输出：

时间复杂性： O（N*N）。本文由 阿努伊·乔汉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章