Advertisement
Guest User

Untitled

a guest
Jul 22nd, 2019
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.12 KB | None | 0 0
  1. import java.util.Arrays;
  2. import java.util.LinkedList;
  3. import java.util.Scanner;
  4.  
  5. public class ccc18j5 {
  6. public static void main(String[] args) {
  7. Scanner sc = new Scanner(System.in);
  8. int N = sc.nextInt();
  9. boolean[][] book = new boolean[N][N];
  10. boolean[] isEnding = new boolean[N];
  11.  
  12. for (int p=0; p<N; p++) { //p is current page
  13. int num = sc.nextInt();
  14. if (num==0) {
  15. isEnding[p] = true;
  16. }
  17. for (int i=0; i<num; i++) {
  18. int nextpage = sc.nextInt()-1; //this is p's next page
  19. book[p][nextpage] = true;
  20. }
  21. }
  22. //step
  23. int[] step = new int[N]; //every page has step
  24. Arrays.fill(step, Integer.MAX_VALUE);
  25. //queue
  26. LinkedList<Integer> queue = new LinkedList<Integer>();
  27. //https://pastebin.com/sgrsZ6vF
  28. //store starting page to queue
  29. queue.add(0);
  30. //set starting page step value to 1
  31. step[0] = 1;
  32. while (!queue.isEmpty()) {
  33. //using poll to read one item from queue
  34. int cur = queue.poll();
  35. //using for loop from book 2D array to
  36. //get all the neighbors
  37. for (int nextpage = 0; nextpage<N; nextpage++) {
  38. if (book[cur][nextpage]==true) {
  39. //go to book array to
  40. //check row cur
  41. //row cur contains all the cur pages next page
  42. if (step[nextpage]>step[cur]+1) {
  43. step[nextpage] = step[cur]+1;
  44. queue.add(nextpage);
  45. }
  46. }
  47. }
  48. }
  49.  
  50. int min = Integer.MAX_VALUE;
  51. boolean reached = true;
  52. for (int i=0; i<N; i++) {
  53. if (step[i]==Integer.MAX_VALUE) {
  54. reached = false;
  55. }
  56. if (isEnding[i] && min>step[i]) {
  57. min = step[i];
  58. }
  59. }
  60. if (reached) {
  61. System.out.println("Y");
  62. } else {
  63. System.out.println("N");
  64. }
  65. System.out.println(min);
  66.  
  67. // 3 number of pages
  68. // 2 2 3 -- represent page 0 next pages
  69. // 0 represent page 1 next pages
  70. // 0
  71.  
  72. //boolean 2D array to store to connection
  73. //book[0][1] = true;
  74. //book[0][2] = true;
  75. // page 1 represent by index 0
  76. // 0 1 2
  77. // 0 true true
  78. // 1
  79. // 2
  80.  
  81. // boolean one D array to store the ending page
  82. // 0 1 2
  83. // false true true
  84.  
  85.  
  86.  
  87. }
  88.  
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement