Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Arrays;
- import java.util.LinkedList;
- import java.util.Scanner;
- public class ccc18j5 {
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- int N = sc.nextInt();
- boolean[][] book = new boolean[N][N];
- boolean[] isEnding = new boolean[N];
- for (int p=0; p<N; p++) { //p is current page
- int num = sc.nextInt();
- if (num==0) {
- isEnding[p] = true;
- }
- for (int i=0; i<num; i++) {
- int nextpage = sc.nextInt()-1; //this is p's next page
- book[p][nextpage] = true;
- }
- }
- //step
- int[] step = new int[N]; //every page has step
- Arrays.fill(step, Integer.MAX_VALUE);
- //queue
- LinkedList<Integer> queue = new LinkedList<Integer>();
- //https://pastebin.com/sgrsZ6vF
- //store starting page to queue
- queue.add(0);
- //set starting page step value to 1
- step[0] = 1;
- while (!queue.isEmpty()) {
- //using poll to read one item from queue
- int cur = queue.poll();
- //using for loop from book 2D array to
- //get all the neighbors
- for (int nextpage = 0; nextpage<N; nextpage++) {
- if (book[cur][nextpage]==true) {
- //go to book array to
- //check row cur
- //row cur contains all the cur pages next page
- if (step[nextpage]>step[cur]+1) {
- step[nextpage] = step[cur]+1;
- queue.add(nextpage);
- }
- }
- }
- }
- int min = Integer.MAX_VALUE;
- boolean reached = true;
- for (int i=0; i<N; i++) {
- if (step[i]==Integer.MAX_VALUE) {
- reached = false;
- }
- if (isEnding[i] && min>step[i]) {
- min = step[i];
- }
- }
- if (reached) {
- System.out.println("Y");
- } else {
- System.out.println("N");
- }
- System.out.println(min);
- // 3 number of pages
- // 2 2 3 -- represent page 0 next pages
- // 0 represent page 1 next pages
- // 0
- //boolean 2D array to store to connection
- //book[0][1] = true;
- //book[0][2] = true;
- // page 1 represent by index 0
- // 0 1 2
- // 0 true true
- // 1
- // 2
- // boolean one D array to store the ending page
- // 0 1 2
- // false true true
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement