fork download
copy 
  1. #include <iostream>
  2. #include<queue>
  3. #include<list>
  4. #include<cstring>
  5. using namespace std;
  6.  
  7. class graph{
  8.  
  9.   int v;
  10.   list<int> *adj;
  11.   public:
  12.   graph(int val)
  13.   {
  14.   	v =val; 
  15.   	adj = new list<int>[v];
  16.   }
  17.   void addEdge(int x,int y)
  18.   {
  19.      adj[x].push_back(y);
  20.   }
  21.  
  22.   bool checkpath(int src,int dest)
  23.   {
  24.   	int *vis =  new int[v];
  25.   	memset(vis,0, v);
  26.   	queue<int >qu;
  27.   	qu.push(src);
  28.   	vis[src]=1;
  29.     while(!qu.empty())
  30.     {
  31.     	int x = qu.front();
  32.     	qu.pop();
  33.     	if(x ==dest)
  34.     	{
  35.     	  cout<<"there is path betw src and dest"<<endl;	
  36.     	 return true;
  37.     	}
  38.  
  39.     	//if(vis[x]==0)
  40.     	//{
  41.     	  //for(int i=0;i<adj[x].size();i++)
  42.     	  for(auto it = adj[x].begin();it!=adj[x].end();it++)
  43.     	  {
  44.     	  	if(*it ==dest)
  45.     	  	return true;
  46.     	  	if(vis[*it]==0)
  47.     	  	{
  48.     	  		qu.push(*it);
  49.     	  		vis[*it]=1;
  50.     	  	}
  51.     	  	else
  52.     	  	{
  53.     	  		cout<<"cycle found"<<endl;
  54.     	  		//return false;
  55.     	  	}
  56.     	  }
  57.     	//}
  58.     }
  59.     return false;
  60.   }
  61.  
  62. };
  63.  
  64. int X[8] = { -2, -1, 1, 2, -2, -1, 1, 2 };
  65. int Y[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };
  66.  
  67.  
  68. void shortestpath(int n,int x,int y,int xt,int yt)
  69. {
  70. 	int vis[n+1][n+1]; 
  71. 	memset(vis,0,sizeof(vis));
  72.  	queue<pair<int,int>> qu;
  73.  	qu.push(make_pair(x,y));
  74.  	int dis[n+1][n+1];
  75.  	//memset(dis,100,sizeof(dis));
  76.  	for (int i = 1; i <= n; i++)
  77.         for (int j = 1; j <= n; j++)
  78.             dis[i][j] = 100;
  79.  
  80.  	int min_setp=100;
  81.  	vis[x][y]=1;
  82.  	while(!qu.empty())
  83.  	{  
  84.  		pair<int,int>vt = qu.front();
  85.  		qu.pop();
  86.  		if(vt.first == xt && vt.second ==yt)
  87.  	    {
  88.  	      	cout<<"target reahched"<<endl;
  89.  	      	break;
  90.  	    }
  91.  	    //cout<<vt.first<<" "<<vt.second<<endl; 
  92.  	    for(int i=0;i<8;i++)
  93.  	    {
  94.  	      int x_tmp = vt.first  + X[i];
  95.  	      int y_tmp = vt.second + Y[i];
  96.  	      if(x_tmp > n || x_tmp <=0 || y_tmp >n || y_tmp <=0)continue;
  97.  	      if(vis[x_tmp][y_tmp]==0)
  98.  	      {
  99.  	      	qu.push(make_pair(x_tmp,y_tmp));
  100.  	      	vis[x_tmp][y_tmp]=1;
  101.  
  102.  	      	if(dis[x_tmp][y_tmp] > dis[x][y] +  1)
  103.  	      	{
  104.  	      		dis[x_tmp][y_tmp] =  dis[x][y] + 1;
  105.  	      	}
  106.  
  107.  	      }
  108.  
  109.  	    }
  110.  	}
  111.  
  112.   cout<<dis[xt][yt]<<endl;
  113. }
  114.  
  115. int main() {
  116. 	// your code goes here
  117. 	graph g(4);
  118.     g.addEdge(0, 1);
  119.     g.addEdge(0, 2);
  120.     g.addEdge(1, 2);
  121.     g.addEdge(2, 0);
  122.     g.addEdge(2, 3);
  123.     g.addEdge(3, 3);
  124.  
  125.     shortestpath(30,1,1,30,30);
  126.    // if(g.checkpath(1,3))
  127.     //cout<<"path excist"<<endl;
  128.     //else cout<<"no path"<<endl;
  129. 	return 0;
  130. }
Success #stdin #stdout 0s 5656KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
target reahched
100
https://ideone.com/isWuni
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!