Advertisement
Guest User

Untitled

a guest
Jan 16th, 2019
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.11 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. public class Task6 {
  4. public static void main(String[] args) {
  5. Scanner scanner = new Scanner(System.in);
  6. int n = scanner.nextInt();
  7. int x1 = scanner.nextInt() - 1;
  8. int y1 = scanner.nextInt() - 1;
  9. int x2 = scanner.nextInt() - 1;
  10. int y2 = scanner.nextInt() - 1;
  11. int[] dx = new int[]{-2, -2, -1, -1, 1, 1, 2, 2};
  12. int[] dy = new int[]{-1, 1, -2, 2, -2, 2, -1, 1};
  13. int[][] d = new int[n][n];
  14. for (int i = 0; i < n; i++) {
  15. for (int j = 0; j < n; j++) {
  16. d[i][j] = -1;
  17. }
  18. }
  19. d[x1][y1] = 0;
  20. Queue<Integer> queue = new LinkedList<>();
  21. queue.offer(x1);
  22. queue.offer(y1);
  23. int ux;
  24. int uy;
  25. int vx;
  26. int vy;
  27. while (!queue.isEmpty()) {
  28. ux = queue.poll();
  29. uy = queue.poll();
  30. for (int i = 0; i < 8; i++) {
  31. vx = ux + dx[i];
  32. vy = uy + dy[i];
  33. if (vx >= 0 && vx < n && vy >= 0 && vy < n && d[vx][vy] == -1) {
  34. d[vx][vy] = d[ux][uy] + 1;
  35. queue.offer(vx);
  36. queue.offer(vy);
  37. }
  38. }
  39. }
  40. System.out.println(d[x2][y2]);
  41. int distance = d[x2][y2];
  42. ux = x2;
  43. uy = y2;
  44. int[][] way = new int[d[x2][y2]+1][2];
  45. for (int i = d[x2][y2]; i >= 0; i--) {
  46. way[i][0] = ux;
  47. way[i][1] = uy;
  48. for (int j = 0; j < 8; j++) {
  49. vx = ux + dx[j];
  50. vy = uy + dy[j];
  51. if (vx >= 0 && vx < n && vy >= 0 && vy < n && d[vx][vy] == distance - 1){
  52. ux = vx;
  53. uy = vy;
  54. distance--;
  55. break;
  56. }
  57. }
  58. }
  59. for (int i = 0; i < way.length; i++) {
  60. for (int j = 0; j < way[i].length; j++) {
  61. System.out.printf("%d ", way[i][j]+1);
  62. }
  63. System.out.println();
  64. }
  65. }
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement