单源路径最短

Problem statement:

问题陈述：

Given a Boolean 2D matrix (0-based index), find whether there is a path from (0,0) to (x,y) and if there is one path, print the minimum no of steps needed to reach it, else print -1 if the destination is not reachable. Moves are possible in only four directions i.e. up, down, left and right. The path can only be created out of a cell if its value is 1.

给定布尔2D矩阵(从0开始的索引)，查找是否存在从(0,0)到(x，y)的路径，如果存在一个路径，则打印达到该路径所需的最少步骤，否则打印如果无法到达目的地，则为-1。 只能沿四个方向移动，即上，下，左和右。 如果路径的值为1，则只能在单元格外部创建路径。

Example:

例：

Matrix dimension: 3X3    Matrix:    1 0 0     1 1 0     0 1 1     Destination point: (2, 2)    Shortest path length to reach destination: 4

Solution

解

Pre-requisites:

先决条件：

1. Defining a point in the maze

1.在迷宫中定义一个点

We need to define a "point" class having two data attributes 1) row no and 2) column no

我们需要定义一个具有两个数据属性的“点”类1)行号和2)列号

class point{    public:    int row;    int column;};

2. Defining node used in solution

2.定义解决方案中使用的节点

A concept of node is used in the solution which actually is an object with two data attributes

解决方案中使用了节点的概念，它实际上是具有两个数据属性的对象

1. A point

   一个点

2. Distance of the point from the source, distance is calculated by path traversed

   点到源的距离，该距离通过所遍历的路径计算

class node{    public:    point p;    int d;};

Algorithm:

算法：

1. Start from the source node. (point (0,0) with a distance 0 )

   从源节点开始。 ( 点(0,0)的距离为0)

2. Declare a queue for BFS traversal.

   声明用于BFS遍历的队列。

3. Check whether a path from the current node is possible or not.

   检查从当前节点开始的路径是否可行。

4. If possible

   如果可能的话

   Mark the node visited.

   将节点标记为已访问。

   EnQueue its neighbour nodes if unvisited

   对未访问的邻居节点进行排队

5. Check for final node to be reached.

   检查要到达的最终节点 。

6. In case of traversing to the neighbour nodes increment node data distance by 1.

   在遍历到相邻节点的情况下，将节点数据距离增加1。

7. Return the final node distance value when final node is reached.

   到达最终节点时，返回最终节点距离值。

8. If all nodes are processed to make the queue empty, then it isn't possible to be reached

   如果处理了所有节点以使队列为空，则不可能到达

   Print -1.

   打印-1。

Since we have use BFS traversal technique it's guaranteed to reach the destination node in minimum no of steps if the destination is reachable from the source node. (point (0, 0)).

由于我们使用了BFS遍历技术，因此如果可以从源节点访问目标，则可以确保以最少的步骤数就可以到达目标节点。 (点(0，0))。

So the steps are:

因此，步骤如下：

1. Checking the base cases

   检查基本情况

   Check whether

   检查是否

   point (0,0) is 0 or not.

   点(0,0)是否为0。

   If it's 0, then we can't make any path from here, so to print -1 & return.

   如果它是0，那么我们不能从这里创建任何路径，因此要打印-1＆return。

2. Initialize Mark[row][col] = false

   初始化Mark [row] [col] = false

   Initially all nodes are unvisited

   最初所有节点均未访问

3. Initialize the queue q

   初始化队列q

4. Create source node & EnQueue(q, source node).

   创建源节点＆ EnQueue(q，源节点) 。

5. Start traversal

   开始遍历

6. While (queue is not empty)  	Temp=DeQueue(q)	IF temp==destination node		printnode distanceand return	END IF	For all neighbour nodes //increment distance by 1		Check whether valid node && unvisited		IFit's a valid node && unvisited			EnQueue(neighbour node, q)			Mark neighbour node visited		END IF	END FOREND WHILE

7. If control comes out of the loop that means destination can't be reached, thus print -1.

   如果控制脱离循环，则意味着无法到达目的地，因此打印-1。

Finding neighbour nodes

寻找邻居节点

All the directions are marked on basis of the current index.

所有方向均根据当前索引进行标记。

• For rightward neighbour-> (row, column+1)

  对于向右邻居->(行，列+1)

• For downward neighbour-> (row+1, column)

  对于向下邻居->(第1行，第1列)

• For leftward neighbour -> (row, column-1)

  对于向左的邻居->(第1列，行)

• For upward neighbour-> (row-1, column)

  对于向上邻居->(第1行，列)

Checking valid node

检查有效节点

If (row of current point<0)    Out of matrix;If (column of current point<0)    Out of matrix;If (row of current point>=m) //m is row no of matrix    Out of matrix;If (column of current point>=n) //n is column no of matrix    Out of matrix;

C ++实现 (C++ implementation)

#include 
    
     using namespace std;//checking valid nodeint isvalid(int nextx,int nexty,int m,int n){
   	if(nextx>=0 && nextx
     
      =0 && nexty
      
        q;	point curr;	//set the source point (0,0)	curr.mpoint(0,0);	node t;	//set the source node at point (0,0)	t.mnode(curr,0); 	//ENQUEUE source node	q.push(t); 	//direction matrices	int arrx[]={
   -1,0,1,0};	int arry[]={
   0,1,0,-1};	point c;	node v;	while(!q.empty()){
   		//DEQUEUE		v=q.front();		c=v.p;		//if destnation node is reached		if(x1==c.row && y1==c.col ){
    			return v.d;		}		q.pop();		//check for all four neighbours		for(int i=0;i<4;i++){
    			int nextx=c.row+arrx[i];			int nexty=c.col+arry[i];			//if valid node && not visited yet			if(isvalid(nextx,nexty,m,n) && a[nextx][nexty] && !visited[nextx][nexty]){
   				curr.mpoint(nextx,nexty);				//set neighbour node by incrementing distance value				t.mnode(curr,(v.d)+1); 				q.push(t); //EnQueue				//mark as visited				visited[nextx][nexty]=true;			}		}	}	return -1;}int main(){
   	int m,n,x,y;	cout<<"enter matrix row & column"<
      
     
    

Output

输出量

First run:enter matrix row & column3 3enter matrix elements (0/1)1 0 01 1 00 1 1enter row & column of destinanation point2 2shortest distance is 4Second run:enter matrix row & column4 4enter matrix elements (0/1)1 0 1 00 0 0 11 1 1 10 1 1 0enter row & column of destinanation point2 3-1no path found

翻译自:

单源路径最短