Want to find the shortest path from source to destination in a 2D maze? Shortest path from source to destination such that edge weights along path are alternatively increasing and decreasing.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | #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 %d\n",shortest(a,m,n,x,y)); else{ cout<<-1<<endl; cout<<"no path found\n"; } return 0; } |
If you like this question & answer and want to contribute, then write your question & answer and email to freewebmentor[@]gmail.com. Your question and answer will appear on FreeWebMentor.com and help other developers.
