算法题：查找矩阵中两个单元之间是否存在路径

本文概述

• Java
• Python3
• C#
• C ++
• Java
• Python3

给定N X N矩阵, 其中用1, 0, 2, 3填充。查找是否存在从源到目标的路径, 仅遍历空白单元格。你可以上下左右移动。

• 单元格的值1表示来源。
• 单元格的值2表示目的地。
• 单元格的值3表示空白单元格。
• 单元格的值0表示空白墙。

注意：只有一个来源和一个目的地(接收器)。

例子：

输入：M [3] [3] = {{0, 3, 2}, {3, 3, 0}, {1, 3, 0}};
输出：是
说明：输入：M [4] [4] = {{0, 3, 1, 0}, {3, 0, 3, 3}, {2, 3, 0, 3}, {0, 3 , 3, 3}};
输出：是
说明：

简单的解决方案：递归。

方法：

在每个矩阵中找到单元的源索引, 然后递归地找到从源索引到矩阵中目标的路径。该算法涉及递归查找所有路径, 直到找到到达目的地的最终路径。

算法：

1. 遍历矩阵并找到矩阵的起始索引。
2. 创建一个采用索引和访问矩阵的递归函数。
3. 标记当前单元格, 然后检查当前单元格是否为目的地。如果当前单元格是目的地, 则返回true。
4. 为所有相邻的空白和未访问单元格调用递归函数。
5. 如果任何递归函数返回true, 则取消标记该单元格并返回true, 否则取消标记该单元格并返回false。

Java

//Java program to find path between two
//cell in matrix
class Path {
 
     //Method for finding and printing
     //whether the path exists or not
     public static void isPath(
         int matrix[][], int n)
     {
         //Defining visited array to keep
         //track of already visited indexes
         boolean visited[][]
             = new boolean [n][n];
 
         //Flag to indicate whether the
         //path exists or not
         boolean flag = false ;
 
         for ( int i = 0 ; i <n; i++) {
             for ( int j = 0 ; j <n; j++) {
                 //if matrix[i][j] is source
                 //and it is not visited
                 if (
                     matrix[i][j] == 1
                     && !visited[i][j])
 
                     //Starting from i, j and
                     //then finding the path
                     if (isPath(
                             matrix, i, j, visited)) {
                         //if path exists
                         flag = true ;
                         break ;
                     }
             }
         }
         if (flag)
             System.out.println( "YES" );
         else
             System.out.println( "NO" );
     }
 
     //Method for checking boundries
     public static boolean isSafe(
         int i, int j, int matrix[][])
     {
 
         if (
             i>= 0 && i <matrix.length
             && j>= 0
             && j <matrix[ 0 ].length)
             return true ;
         return false ;
     }
 
     //Returns true if there is a
     //path from a source (a
     //cell with value 1) to a
     //destination (a cell with
     //value 2)
     public static boolean isPath(
         int matrix[][], int i, int j, boolean visited[][])
     {
 
         //Checking the boundries, walls and
         //whether the cell is unvisited
         if (
             isSafe(i, j, matrix)
             && matrix[i][j] != 0
             && !visited[i][j]) {
             //Make the cell visited
             visited[i][j] = true ;
 
             //if the cell is the required
             //destination then return true
             if (matrix[i][j] == 2 )
                 return true ;
 
             //traverse up
             boolean up = isPath(
                 matrix, i - 1 , j, visited);
 
             //if path is found in up
             //direction return true
             if (up)
                 return true ;
 
             //traverse left
             boolean left
                 = isPath(
                     matrix, i, j - 1 , visited);
 
             //if path is found in left
             //direction return true
             if (left)
                 return true ;
 
             //traverse down
             boolean down = isPath(
                 matrix, i + 1 , j, visited);
 
             //if path is found in down
             //direction return true
             if (down)
                 return true ;
 
             //traverse right
             boolean right
                 = isPath(
                     matrix, i, j + 1 , visited);
 
             //if path is found in right
             //direction return true
             if (right)
                 return true ;
         }
         //no path has been found
         return false ;
     }
 
     //driver program to
     //check above function
     public static void main(String[] args)
     {
 
         int matrix[][] = { { 0 , 3 , 0 , 1 }, { 3 , 0 , 3 , 3 }, { 2 , 3 , 3 , 3 }, { 0 , 3 , 3 , 3 } };
 
         //calling isPath method
         isPath(matrix, 4 );
     }
}
 
/* This code is contributed by Madhu Priya */

Python3

# Python3 program to find
# path between two cell in matrix
 
# Method for finding and printing
# whether the path exists or not
def isPath(matrix, n):
 
     # Defining visited array to keep
     # track of already visited indexes
     visited = [[ False for x in range (n)]
                       for y in range (n)]
    
     # Flag to indicate whether the
     # path exists or not
     flag = False
 
     for i in range (n):
         for j in range (n):
           
             # If matrix[i][j] is source
             # and it is not visited
             if (matrix[i][j] = = 1 and not
                 visited[i][j]):
 
                 # Starting from i, j and
                 # then finding the path
                 if (checkPath(matrix, i, j, visited)):
                   
                     # If path exists
                     flag = True
                     break
     if (flag):
         print ( "YES" )
     else :
         print ( "NO" )
 
# Method for checking boundries
def isSafe(i, j, matrix):
   
     if (i> = 0 and i <len (matrix) and
         j> = 0 and j <len (matrix[ 0 ])):
         return True
     return False
 
# Returns true if there is a
# path from a source(a
# cell with value 1) to a
# destination(a cell with
# value 2)
def checkPath(matrix, i, j, visited):
 
     # Checking the boundries, walls and
     # whether the cell is unvisited
     if (isSafe(i, j, matrix) and
         matrix[i][j] ! = 0 and not
         visited[i][j]):
       
         # Make the cell visited
         visited[i][j] = True
 
         # If the cell is the required
         # destination then return true
         if (matrix[i][j] = = 2 ):
            return True
 
         # traverse up
         up = checkPath(matrix, i - 1 , j, visited)
 
         # If path is found in up
         # direction return true
         if (up):
            return True
 
         # Traverse left
         left = checkPath(matrix, i, j - 1 , visited)
 
         # If path is found in left
         # direction return true
         if (left):
            return True
 
         # Traverse down
         down = checkPath(matrix, i + 1 , j, visited)
 
         # If path is found in down
         # direction return true
         if (down):
            return True
 
         # Traverse right
         right = checkPath(matrix, i, j + 1 , visited)
 
         # If path is found in right
         # direction return true
         if (right):
            return True
     
     # No path has been found
     return False
 
# Driver code
if __name__ = = "__main__" :
   
     matrix = [[ 0 , 3 , 0 , 1 ], [ 3 , 0 , 3 , 3 ], [ 2 , 3 , 3 , 3 ], [ 0 , 3 , 3 , 3 ]]
 
     # calling isPath method
     isPath(matrix, 4 )
 
# This code is contributed by Chitranayal

C#

//C# program to find path between two
//cell in matrix
using System;
 
class GFG{
 
//Method for finding and printing
//whether the path exists or not
static void isPath( int [, ] matrix, int n)
{
     
     //Defining visited array to keep
     //track of already visited indexes
     bool [, ] visited = new bool [n, n];
     
     //Flag to indicate whether the
     //path exists or not
     bool flag = false ;
 
     for ( int i = 0; i <n; i++)
     {
         for ( int j = 0; j <n; j++)
         {
             
             //If matrix[i][j] is source
             //and it is not visited
             if (matrix[i, j] == 1 &&
               !visited[i, j])
               
                 //Starting from i, j and
                 //then finding the path
                 if (isPath(matrix, i, j, visited))
                 {
                     
                     //If path exists
                     flag = true ;
                     break ;
                 }
         }
     }
     if (flag)
         Console.WriteLine( "YES" );
     else
         Console.WriteLine( "NO" );
}
 
//Method for checking boundries
public static bool isSafe( int i, int j, int [, ] matrix)
{
     if (i>= 0 && i <matrix.GetLength(0) &&
         j>= 0 && j <matrix.GetLength(1))
         return true ;
         
     return false ;
}
 
//Returns true if there is a path from
//a source (a cell with value 1) to a
//destination (a cell with value 2)
public static bool isPath( int [, ] matrix, int i, int j, bool [, ] visited)
{
     
     //Checking the boundries, walls and
     //whether the cell is unvisited
     if (isSafe(i, j, matrix) &&
            matrix[i, j] != 0 &&
          !visited[i, j])
     {
         
         //Make the cell visited
         visited[i, j] = true ;
 
         //If the cell is the required
         //destination then return true
         if (matrix[i, j] == 2)
             return true ;
 
         //Traverse up
         bool up = isPath(matrix, i - 1, j, visited);
 
         //If path is found in up
         //direction return true
         if (up)
             return true ;
 
         //Traverse left
         bool left = isPath(matrix, i, j - 1, visited);
 
         //If path is found in left
         //direction return true
         if (left)
             return true ;
 
         //Traverse down
         bool down = isPath(matrix, i + 1, j, visited);
 
         //If path is found in down
         //direction return true
         if (down)
             return true ;
 
         //Traverse right
         bool right = isPath(matrix, i, j + 1, visited);
 
         //If path is found in right
         //direction return true
         if (right)
             return true ;
     }
     
     //No path has been found
     return false ;
}
 
//Driver code  
static void Main()
{
     int [, ] matrix = { { 0, 3, 0, 1 }, { 3, 0, 3, 3 }, { 2, 3, 3, 3 }, { 0, 3, 3, 3 } };
 
     //Calling isPath method
     isPath(matrix, 4);
}
}
 
//This code is contributed by divyeshrabadiya07

输出如下：

YES

复杂度分析：

• 时间复杂度：O(4n * m)。
  对于每个单元, 可以有4个相邻的未访问单元, 因此时间复杂度为O(4n * m)。
• 空间复杂度：O(n * m)
  需要空间来存储访问数组。

高效的解决方案：

图形。

方法：

这个想法是使用

广度优先搜索

。将每个单元视为一个节点, 并将任何两个相邻单元之间的每个边界作为一条边。所以Node的总数是N *N。

因此, 想法是从起始单元格开始进行广度优先搜索, 直到找到终止单元格。

算法：

1. 创建一个具有N * N个节点(顶点)的空图, 将所有节点推入图中, 并记下源顶点和宿顶点。
2. 现在在图上应用BFS, 创建一个队列并将源节点插入该队列中
3. 运行循环, 直到队列大小大于0
4. 删除队列的最前面的节点, 如果目标返回true, 则检查该节点是否为目标。标记节点
5. 检查所有相邻的单元格(如果未访问), 并将它们空白插入队列。
6. 如果未到达目的地, 则返回true。

C ++

//C++ program to find path
//between two cell in matrix
#include <bits/stdc++.h>
using namespace std;
#define N 4
 
class Graph {
     int V;
     list<int>* adj;
 
public :
     Graph( int V)
     {
         this ->V = V;
         adj = new list<int>[V];
     }
     void addEdge( int s, int d);
     bool BFS( int s, int d);
};
 
//add edge to graph
void Graph::addEdge( int s, int d)
{
     adj展开.push_back(d);
}
 
//BFS function to find path
//from source to sink
bool Graph::BFS( int s, int d)
{
     //Base case
     if (s == d)
         return true ;
 
     //Mark all the vertices as not visited
     bool * visited = new bool [V];
     for ( int i = 0; i <V; i++)
         visited[i] = false ;
 
     //Create a queue for BFS
     list<int> queue;
 
     //Mark the current node as visited and
     //enqueue it
     visited展开 = true ;
     queue.push_back(s);
 
     //it will be used to get all adjacent
     //vertices of a vertex
     list<int>::iterator i;
 
     while (!queue.empty()) {
         //Dequeue a vertex from queue
         s = queue.front();
         queue.pop_front();
 
         //Get all adjacent vertices of the
         //dequeued vertex s. If a adjacent has
         //not been visited, then mark it visited
         //and enqueue it
         for (
             i = adj展开.begin(); i != adj展开.end(); ++i) {
             //If this adjacent node is the
             //destination node, then return true
             if (*i == d)
                 return true ;
 
             //Else, continue to do BFS
             if (!visited[*i]) {
                 visited[*i] = true ;
                 queue.push_back(*i);
             }
         }
     }
 
     //If BFS is complete without visiting d
     return false ;
}
 
bool isSafe( int i, int j, int M[][N])
{
     if (
         (i <0 || i>= N)
         || (j <0 || j>= N)
         || M[i][j] == 0)
         return false ;
     return true ;
}
 
//Returns true if there is
//a path from a source (a
//cell with value 1) to a
//destination (a cell with
//value 2)
bool findPath( int M[][N])
{
     //source and destination
     int s, d;
     int V = N * N + 2;
     Graph g(V);
 
     //create graph with n*n node
     //each cell consider as node
     //Number of current vertex
     int k = 1;
     for ( int i = 0; i <N; i++) {
         for ( int j = 0; j <N; j++) {
             if (M[i][j] != 0) {
                 //connect all 4 adjacent
                 //cell to current cell
                 if (isSafe(i, j + 1, M))
                     g.addEdge(k, k + 1);
                 if (isSafe(i, j - 1, M))
                     g.addEdge(k, k - 1);
                 if (i <N - 1 && isSafe(i + 1, j, M))
                     g.addEdge(k, k + N);
                 if (i> 0 && isSafe(i - 1, j, M))
                     g.addEdge(k, k - N);
             }
 
             //Source index
             if (M[i][j] == 1)
                 s = k;
 
             //Destination index
             if (M[i][j] == 2)
                 d = k;
             k++;
         }
     }
 
     //find path Using BFS
     return g.BFS(s, d);
}
 
//driver program to check
//above function
int main()
{
     int M[N][N] = { { 0, 3, 0, 1 }, { 3, 0, 3, 3 }, { 2, 3, 3, 3 }, { 0, 3, 3, 3 } };
 
     (findPath(M) == true ) ? cout <<"Yes" : cout <<"No" <<endl;
 
     return 0;
}

Java

//Java program to find path between two
//cell in matrix
import java.util.*;
 
class Graph {
     int V;
     List<List<Integer>> adj;
 
     Graph( int V)
     {
         this .V = V;
         adj = new ArrayList<>(V);
         for ( int i = 0 ; i <V; i++) {
             adj.add(i, new ArrayList<>());
         }
     }
 
     //add edge to graph
     void addEdge( int s, int d)
     {
         adj.get(s).add(d);
     }
 
     //BFS function to find path
     //from source to sink
     boolean BFS( int s, int d)
     {
         //Base case
         if (s == d)
             return true ;
 
         //Mark all the vertices as not visited
         boolean [] visited = new boolean [V];
 
         //Create a queue for BFS
         Queue<Integer> queue
             = new LinkedList<>();
 
         //Mark the current node as visited and
         //enqueue it
         visited展开 = true ;
         queue.offer(s);
 
         //it will be used to get all adjacent
         //vertices of a vertex
         List<Integer> edges;
 
         while (!queue.isEmpty()) {
             //Dequeue a vertex from queue
             s = queue.poll();
 
             //Get all adjacent vertices of the
             //dequeued vertex s. If a adjacent has
             //not been visited, then mark it visited
             //and enqueue it
             edges = adj.get(s);
             for ( int curr : edges) {
                 //If this adjacent node is the
                 //destination node, then return true
                 if (curr == d)
                     return true ;
 
                 //Else, continue to do BFS
                 if (!visited[curr]) {
                     visited[curr] = true ;
                     queue.offer(curr);
                 }
             }
         }
 
         //If BFS is complete without visiting d
         return false ;
     }
 
     static boolean isSafe(
         int i, int j, int [][] M)
     {
         int N = M.length;
         if (
             (i <0 || i>= N)
             || (j <0 || j>= N)
             || M[i][j] == 0 )
             return false ;
         return true ;
     }
 
     //Returns true if there is a
     //path from a source (a
     //cell with value 1) to a
     //destination (a cell with
     //value 2)
     static boolean findPath( int [][] M)
     {
         //Source and destination
         int s = - 1 , d = - 1 ;
         int N = M.length;
         int V = N * N + 2 ;
         Graph g = new Graph(V);
 
         //Create graph with n*n node
         //each cell consider as node
         int k = 1 ; //Number of current vertex
         for ( int i = 0 ; i <N; i++) {
             for ( int j = 0 ; j <N; j++) {
                 if (M[i][j] != 0 ) {
 
                     //connect all 4 adjacent
                     //cell to current cell
                     if (isSafe(i, j + 1 , M))
                         g.addEdge(k, k + 1 );
                     if (isSafe(i, j - 1 , M))
                         g.addEdge(k, k - 1 );
                     if (i <N - 1
                         && isSafe(i + 1 , j, M))
                         g.addEdge(k, k + N);
                     if (i> 0 && isSafe(i - 1 , j, M))
                         g.addEdge(k, k - N);
                 }
 
                 //source index
                 if (M[i][j] == 1 )
                     s = k;
 
                 //destination index
                 if (M[i][j] == 2 )
                     d = k;
                 k++;
             }
         }
 
         //find path Using BFS
         return g.BFS(s, d);
     }
 
     //Driver program to check above function
     public static void main(
         String[] args) throws Exception
     {
         int [][] M = { { 0 , 3 , 0 , 1 }, { 3 , 0 , 3 , 3 }, { 2 , 3 , 3 , 3 }, { 0 , 3 , 3 , 3 } };
 
         System.out.println(
             ((findPath(M)) ? "Yes" : "No" ));
     }
}
 
//This code is contributed by abhay379201

Python3

# Python3 program to find path between two
# cell in matrix
from collections import defaultdict
class Graph:
     def __init__( self ):
         self .graph = defaultdict( list )
     
     # add edge to graph
     def addEdge( self , u, v):
         self .graph[u].append(v)
 
     # BFS function to find path from source to sink    
     def BFS( self , s, d):
         
         # Base case
         if s = = d:
             return True
             
         # Mark all the vertices as not visited
         visited = [ False ] * ( len ( self .graph) + 1 )
 
         # Create a queue for BFS
         queue = []
         queue.append(s)
 
         # Mark the current node as visited and
         # enqueue it
         visited展开 = True
         while (queue):
 
             # Dequeue a vertex from queue
             s = queue.pop( 0 )
 
             # Get all adjacent vertices of the
             # dequeued vertex s. If a adjacent has
             # not been visited, then mark it visited
             # and enqueue it
             for i in self .graph展开:
                 
                 # If this adjacent node is the destination
                 # node, then return true
                 if i = = d:
                     return True
 
                 # Else, continue to do BFS
                 if visited[i] = = False :
                     queue.append(i)
                     visited[i] = True
 
         # If BFS is complete without visiting d
         return False
 
def isSafe(i, j, matrix):
     if i> = 0 and i <= len (matrix) and j> = 0 and j <= len (matrix[ 0 ]):
         return True
     else :
         return False
 
# Returns true if there is a path from a source (a
# cell with value 1) to a destination (a cell with
# value 2)
def findPath(M):
     s, d = None , None # source and destination
     N = len (M)
     g = Graph()
 
     # create graph with n * n node
     # each cell consider as node
     k = 1 # Number of current vertex
     for i in range (N):
         for j in range (N):
             if (M[i][j] ! = 0 ):
 
                 # connect all 4 adjacent cell to
                 # current cell
                 if (isSafe(i, j + 1 , M)):
                     g.addEdge(k, k + 1 )
                 if (isSafe(i, j - 1 , M)):
                     g.addEdge(k, k - 1 )
                 if (isSafe(i + 1 , j, M)):
                     g.addEdge(k, k + N)
                 if (isSafe(i - 1 , j, M)):
                     g.addEdge(k, k - N)
             
             if (M[i][j] = = 1 ):
                 s = k
 
             # destination index    
             if (M[i][j] = = 2 ):
                 d = k
             k + = 1
 
     # find path Using BFS
     return g.BFS(s, d)
 
# Driver code
if __name__ = = '__main__' :
     M = [[ 0 , 3 , 0 , 1 ], [ 3 , 0 , 3 , 3 ], [ 2 , 3 , 3 , 3 ], [ 0 , 3 , 3 , 3 ]]
     if findPath(M):
         print ( "Yes" )
     else :
         print ( "No" )
 
# This Code is Contributed by Vikash Kumar 37

输出如下：

Yes

复杂度分析：

• 时间复杂度：O(n * m)
  矩阵的每个单元仅被访问一次, 因此时间复杂度为O(n * m)。
• 空间复杂度：O(n * m)
  需要空间来存储访问的数组并创建队列。