Fuente menor a la ruta de destino

En este artículo, vamos a ver cómo encontrar el camino más corto desde el origen al destino en un laberinto 2D ? Este problema ha sido presentado en la ronda de codificación de Samsung.

declaración Problema:

Dada una matriz booleana 2D (0-basado índice), encontrar si existe un camino desde (0,0) a (x, y) y if hay un camino, sin imprimir el mínimo de pasos necesarios para llegar a él, else de impresión -1 if el destino no es alcanzable. Movimientos son posibles sólo en cuatro direcciones es decir, hacia arriba, abajo, izquierda y derecha. La ruta de acceso sólo puede ser creado a partir de una célula if su valor es 1.

Ejemplo:

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

Solución

Pre-requisitos:

1. Definición de un punto en el laberinto

necesitamos definir un “punto” clase que tiene dos atributos de datos 1) fila no y 2) la columna no

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

2. Definición de nodo utilizado en solución

un concepto de nodo se utiliza en la solución que en realidad es un objeto con dos atributos de datos

  1. un punto
  2. distancia del punto de la fuente, la distancia se calcula camino recorrido

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

Algoritmo:

  1. de inicio desde el nodo fuente. ( punto (0,0) con una distancia 0)
  2. Declarar una cola para BFS traversal.
  3. Comprobar si una ruta desde el nodo actual es posible o no.
  4. If posible
    marca el nodo visitado.
    Enqueue su vecino no visitado nodos if
  5. Compruebe nudo final a alcanzar.
  6. En case de atravesar al vecino nodos de datos de nodo de incremento distancia por 1.
  7. Return el valor de distancia nodo final cuando se alcanza el nodo final.
  8. If todos los nodos se procesan para hacer la cola vacía, entonces no es posible que se alcance
    Imprimir -1.

Desde que tenemos uso de la técnica de recorrido de BFS está garantizado para llegar al nodo de destino en el mínimo de pasos sin if el destino es alcanzable desde el nodo de origen. (Punto (0, 0)).

Así que los pasos son:

  1. Comprobación de los casos base
    Compruebe si punto (0,0) es 0 o no.
    If es 0, entonces no podemos hacer ningún camino desde aquí, así que para imprimir -1 y return.
  2. Inicializar Marcos [fila] [col] = falsos
    Inicialmente todos los nodos son unvisited
  3. Inicializar la cola q
  4. Crear nodo de origen y poner en cola (q, nodo de origen) .
  5. de inicio de recorrido
  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 FOR
    END WHILE

  7. If de control sale del bucle que los medios de destino no puede ser alcanzado, por lo tanto imprimir -1.

Finding vecino nodos

Shortest Source to Destination Path - 4

Todas las direcciones están marcadas en función del índice actual.

  • Para hacia la derecha de Neighbour> (fila, columna + 1)
  • Para Neighbour hacia abajo> (fila + 1, columna)
  • Para vecino hacia la izquierda -> (fila, columna-1)
  • Para Neighbour hacia arriba> (fila-1, columna)

Comprobación de nodo válido

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 ++ aplicación

#include <bits/stdc++.h>
using namespace std;
//checking valid node
int isvalid(int nextx,int nexty,int m,int n){
if(nextx>=0 && nextx<m && nexty>=0 && nexty<n)
return 1;
return 0;
}
//defining point
class point{
public:
int row;
int col;
//make point
void mpoint(int m,int n){
row=m;
col=n;
}
};
//defining node
class node{
public:
point p;
int d;
void mnode(point q,int dis){ //make node
p.row=q.row;
p.col=q.col;
d=dis;
}
};
//finding shortest path
int shortest(int** a,int m,int n,int x1,int y1){
if(a[0][0]==0)//base case
return -1;
bool visited[m][n];
//initialize
memset(visited,false,sizeof(visited));
//declare queue by STL
queue<node> 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"<<endl;
scanf("%d %d",&m,&n);
int **a=(int**)malloc(sizeof(int*)*m);
for(int i=0;i<m;i++)
a[i]=(int*)(malloc(sizeof(int)*n));
cout<<"enter matrix elements (0/1)"<<endl;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
scanf("%d",&a[i][j]);
cout<<"enter row & column of destinanation point"<<endl;
scanf("%d %d",&x,&y);
if(shortest(a,m,n,x,y)!=-1)//if path found
printf("shortest distance is %dn",shortest(a,m,n,x,y));
else{
cout<<-1<<endl;
cout<<"no path foundn";
}
return 0;
}

salida

First run:
enter matrix row & column
3 3
enter matrix elements (0/1)
1 0 0
1 1 0
0 1 1
enter row & column of destinanation point
2 2
shortest distance is 4
Second run:
enter matrix row & column
4 4
enter matrix elements (0/1)
1 0 1 0
0 0 0 1
1 1 1 1
0 1 1 0
enter row & column of destinanation point
2 3
-1
no path found

mensajes recomendados

  • punto de salida en una matriz
  • matriz cadena
  • Gold Mine Problema
  • Rellena 8 números en una matriz
  • Encuentra la magia matriz
  • de longitud de ejecución codificar (hallazgo de frecuencias / impresión de letras en una cadena)
  • Ordenar una serie de 0 de 1, de 2 y de la complejidad en tiempo lineal
  • subarreglo Finding con determinada suma
  • 1 [0] 1 Patrón Conde
  • Greedy estrategia para resolver los principales problemas del algoritmo
  • problema de secuenciación de empleo
  • punto de salida en una matriz
  • Generar código Gray Secuencias
  • números Picking
  • Conde y Say secuencia


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *