fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6. typedef pair<int, int> p;
  7.  
  8. int bfs(int y, int x);
  9.  
  10. int size, y1,x1,y2,x2;
  11. int dy[] = {-2,-2,-1,-1,1,1,2,2};
  12. int dx[] = {-1,1,-2,2,-2,2,-1,1};
  13.  
  14. int main() {
  15. 	// your code goes here
  16. 	int tc;
  17. 	cin.tie(0);
  18. 	cin.sync_with_stdio(0);
  19. 	cin>>tc;
  20. 	while(tc--){
  21. 		cin>>size>>y1>>x1>>y2>>x2;
  22. 		int cnt = bfs(y1,x1);
  23. 		cout<<cnt<<'\n';
  24.  
  25. 	}
  26. 	return 0;
  27. }
  28.  
  29. int bfs(int y, int x){
  30. 	bool field[size][size];
  31. 	for(int i=0; i<size; i++)
  32. 		for(int j = 0; j<size; j++)
  33. 			field[i][j] = 0;
  34. 	queue<pair<p, int>> q;
  35. 	field[y][x] = 1;
  36. 	q.push({{y,x}, 0});
  37. 	while(q.size()){
  38. 		int cury = q.front().first.first;
  39. 		int curx = q.front().first.second;
  40. 		int curm = q.front().second;
  41. 		q.pop();
  42. 		if(cury==y2&&curx==x2) return curm;
  43.  
  44. 		for(int i=0; i<8; i++){
  45. 			int ny = cury+dy[i];
  46. 			int nx = curx+dx[i];
  47. 			if(ny<0||nx<0||ny>=size||nx>=size) continue;
  48. 			if(!field[ny][nx]){
  49. 				field[ny][nx]=1;
  50. 				q.push({{ny,nx}, curm+1});
  51. 			}
  52. 		}
  53.  
  54. 	}
  55.  
  56. }
Success #stdin #stdout 0.01s 5460KB
comments (?)
stdin
copy 
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
stdout
copy 
5
28
0
https://ideone.com/HwpXOK
language:
C++ (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!