AOJ 2332: 時空のスゴロク・ロード (幅優先探索)

問題

Space-Time Sugoroku Road | Aizu Online Judge

解法

幅優先探索。各マスに到達するのに必要な最小回数を更新した時だけキューに入れるようにすれば、ループを避けることが出来る。

コード

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] cells = new int[N];
		for (int i = 0; i < cells.length; i++) {
			cells[i] = sc.nextInt();
		}
		sc.close();

		Deque<Integer> bfs = new ArrayDeque<Integer>();
		bfs.add(0);
		int[] min = new int[N];
		Arrays.fill(min, 10000000);
		min[0] = 0;
		while (!bfs.isEmpty()) {
			int poll = bfs.pollFirst();
			if (cells[poll] == 0) {
				for (int d = 1; d <= 6; d++) {
					int jump = Math.min(poll + d, N - 1);
					if (min[jump] > min[poll] + 1) {
						min[jump] = min[poll] + 1;
						bfs.addLast(jump);
					}
				}
			} else {
				int jump = poll + cells[poll];
				if (min[jump] > min[poll]) {
					min[jump] = min[poll];
					bfs.addFirst(jump);
				}
			}
		}
		System.out.println(min[N - 1]);

	}
}