EvbCFfp1XB

problem and my answer.

March 2013

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);
}
}
}


This is a template of method rangeCheck.

source code

    /**
* Returns if the given value is in the given range.
*
* @param i
* the value to be tested
* @param min
* the minimum of range
* @param max
* the maximum of range
* @return true if i is between min and max, inclusive
* @throws IllegalArgumentException
* if min &gt; max
*/
private static final boolean rangeCheck(int i, int min, int max) {
if (min > max) {
throw new IllegalArgumentException("min must not be greater than max.");
}
return min <= i && i <= max;
}

このページのトップヘ