fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int dx[] = {-1,-1,1,1,-2,-2,2,2};
  5. const int dy[] = {-2,2,-2,2,-1,1,-1,1};
  6.  
  7. struct point
  8. {
  9. 	int x, y; 
  10. };
  11.  
  12. int x1, y1, x2, y2, head, tail, d[ 9 ][ 9 ], size = 0;
  13. point p[ 9 ][ 9 ];
  14.  
  15. bool valid( int x, int y )
  16. {
  17. 	return x > 0 && x < 9 && y > 0 && y < 9 && d[ x ][ y ] == -1;
  18. }
  19.  
  20. int main()
  21. {
  22. 	cin >> x1 >> y1 >> x2 >> y2;
  23.  
  24. 	point q[ 9 * 9 ],ans[ 9 * 9 ],cur,st;
  25. 	q[ 0 ].x = x1;
  26. 	q[ 0 ].y = y1;
  27. 	head = tail = 0;
  28.  
  29. 	for ( int i = 0; i < 9; ++i )
  30. 		for ( int j = 0; j < 9; ++j )
  31. 		{
  32. 			d[ i ][ j ] = -1;
  33. 			p[ i ][ j ].x = p[ i ][ j ].y = -1;
  34. 		}
  35.  
  36. 	d[ x1 ][ y1 ] = 0;
  37. 	while ( head <= tail )
  38. 	{
  39. 		cur = st = q[ head++ ];
  40. 		for ( int i = 0; i < 8; ++i )
  41. 		{
  42. 			cur.x = st.x + dx[i], cur.y = st.y + dy[ i ];
  43. 			if ( valid( cur.x, cur.y ) )
  44. 			{
  45. 				q[ ++tail ] = cur;
  46. 				d[ cur.x ][ cur.y ] = d[ st.x ][ st. y ] + 1;
  47. 				p[ cur.x ][ cur.y ] = st;
  48. 			}
  49. 		}
  50. 	}
  51.  
  52. 	cout << "Length of path is " << d[ x2 ][ y2 ] << "\n";
  53.  
  54. 	cout << "Path:\n";
  55.  
  56. 	point u;
  57. 	u.x = x2;
  58. 	u.y = y2;
  59.  
  60. 	for ( ; u.x != -1 && u.y != -1; u = p[ u .x ][ u.y ] ) 
  61. 		ans[ ++size ] = u;
  62.  
  63. 	for ( int i = size; i > 0; --i )
  64. 		cout << ans[ i ].x << " " << ans[ i ].y << "\n";
  65.  
  66. 	return 0;
  67. }
  68.  
Success #stdin #stdout 0s 3144KB
comments (?)
stdin
copy 
1 1
3 5
stdout
copy 
Length of path is 2
Path:
1 1
2 3
3 5
https://ideone.com/co0bok
language:
C++14 (gcc 8.3)
created:
11 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!