本文概述
给定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}};
输出：是
说明：
简单的解决方案：递归。
方法：
在每个矩阵中找到单元的源索引, 然后递归地找到从源索引到矩阵中目标的路径。该算法涉及递归查找所有路径, 直到找到到达目的地的最终路径。
算法：
- 遍历矩阵并找到矩阵的起始索引。
- 创建一个采用索引和访问矩阵的递归函数。
- 标记当前单元格, 然后检查当前单元格是否为目的地。如果当前单元格是目的地, 则返回true。
- 为所有相邻的空白和未访问单元格调用递归函数。
- 如果任何递归函数返回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 ChitranayalC#
//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。
因此, 想法是从起始单元格开始进行广度优先搜索, 直到找到终止单元格。
算法：
- 创建一个具有N * N个节点(顶点)的空图, 将所有节点推入图中, 并记下源顶点和宿顶点。
- 现在在图上应用BFS, 创建一个队列并将源节点插入该队列中
- 运行循环, 直到队列大小大于0
- 删除队列的最前面的节点, 如果目标返回true, 则检查该节点是否为目标。标记节点
- 检查所有相邻的单元格(如果未访问), 并将它们空白插入队列。
- 如果未到达目的地, 则返回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 abhay379201Python3
# 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)
需要空间来存储访问的数组并创建队列。
![从字法上最小长度N的排列，使得对于正好为K个索引，a[i] a[i]+1](https://www.lsbin.com/wp-content/themes/begin%20lts/img/loading.png)
