**problem**AOJ 0262: Making Sugoroku

**how to solve**NG if the position can be reached and can not reach the goal.

**source code**

import java.util.Arrays;

import java.util.Scanner;

public class MakingSugoroku {

public static void main(String[] args) {

new MakingSugoroku().run();

}

int n;

int[] move;

int max;

private void run() {

Scanner sc = new Scanner(System.in);

for (; sc.hasNext();) {

int a = sc.nextInt();

if (a == 0) {

break;

}

max = a;

n = sc.nextInt();

move = new int[n];

for (int i = 0; i < move.length; i++) {

move[i] = sc.nextInt();

}

solve();

}

sc.close();

}

int[] newmove;

private void solve() {

newmove = new int[n + 2];

for (int i = 0; i < move.length; i++) {

newmove[i + 1] = move[i];

}

boolean[] reached = new boolean[n + 2];

Arrays.fill(reached, false);

dfs(0, reached);

int[][] nextTable = new int[n + 2][max];

for (int i = 0; i < nextTable.length; i++) {

for (int j = 0; j < max; j++) {

int nextPosition = Math.max(0, Math.min(n + 1, i + (j + 1)));

int nextPlusMove = Math.max(0, Math.min(n + 1, nextPosition + newmove[nextPosition]));

nextTable[i][j] = nextPlusMove;

}

}

boolean[] reachGoal = new boolean[n + 2];

Arrays.fill(reachGoal, false);

reachGoal[n + 1] = true;

for (;;) {

boolean change = false;

for (int i = 0; i < nextTable.length; i++) {

if (!reachGoal[i]) {

for (int j = 0; j < nextTable[i].length; j++) {

if (reachGoal[nextTable[i][j]]) {

reachGoal[i] = true;

change = true;

}

}

}

}

if (!change) {

break;

}

}

boolean isNG = false;

for (int i = 0; i < reachGoal.length; i++) {

if (reached[i] && !reachGoal[i]) {

isNG = true;

}

}

if (isNG) {

System.out.print("NG" + "\n");

} else {

System.out.print("OK" + "\n");

}

}

private void dfs(int i, boolean[] reached) {

if (reached[i]) {

return;

}

if (i == n + 1) {

return;

}

reached[i] = true;

for (int j = 0; j < max; j++) {

int nextPosition = Math.max(0, Math.min(n + 1, i + (j + 1)));

int nextPlusMove = Math.max(0, Math.min(n + 1, nextPosition + newmove[nextPosition]));

dfs(nextPlusMove, reached);

}

}

}