EvbCFfp1XB

problem and my answer.

November 2012

problem AOJ 0247:   Ice Maze

how to solve I use breadth-first search.

source code

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;

public class IceMaze {
private static boolean test = !true;

public static void main(String[] args) {
if (test) {
testA();
testB();
testC();
testD();
testE();
for (;;)
testZ();
} else {
run();
}
}

private static void testA() {
test("A", "5 5\n" + ".X.S.\n" + ".X#..\n" + ".XX##\n" + ".#XG.\n"
+ "..X..\n", "11");
}

private static void testB() {
test("B", "7 3\n" + "SXX.XXG\n" + "X.#.#X.\n" + "XXX.XX#\n", "10");
}

private static void testC() {
test("C", "4 4\n" + "S...\n" + "X.X.\n" + "GX..\n" + "...X\n", "10");
}

private static void testD() {
test("D", "10 10\n" + "..XXXXX.XX\n" + ".X.#.#X.XX\n" + "SX.#X.X..X\n"
+ "#X.##.X.XX\n" + "..XXXX#.XX\n" + "##.##.##XX\n"
+ "....X.XX#X\n" + ".##X..#X#X\n" + "....XX#..X\n"
+ "...#XXG..X\n", "33");
}

private static void testE() {
test("E", "12 12\n" + ".X....X..X.X\n" + "#X.#X.X.XX.X\n"
+ "##X.XX..###X\n" + ".XX##X.#..XX\n" + ".X.XXXX...XX\n"
+ "#XX#..XX.XX.\n" + "..XXX#.X###S\n" + "X#..##XX.XX.\n"
+ "X#X.XXX.XX.X\n" + ".X.X###...#X\n" + "#XXXX#G##X.#\n"
+ "XX.....#XXX#\n", "17");
}

private static void testZ() {
StringBuilder sb = new StringBuilder();
int x = 12;
int y = 12;
sb.append(x + " " + y + "\n");
int si = randomInt(1, y - 1 - 1);
int sj = randomInt(1, x - 1 - 1);
int gi = randomInt(1, y - 1 - 1);
int gj = randomInt(1, x - 1 - 1);
while (si == gi && sj == gj) {
gi = randomInt(1, y - 1 - 1);
gj = randomInt(1, x - 1 - 1);
}
String[] v = new String[] { ".", "#", "X", "X", };
String[][] s = new String[y][x];
for (int i = 0; i < y; i++) {
for (int j = 0; j < x; j++) {
s[i][j] = randomInt(v);
}
}
s[si][sj] = "S";
s[si - 1][sj] = ".";
s[si][sj - 1] = ".";
s[si + 1][sj] = ".";
s[si][sj + 1] = ".";
s[gi][gj] = "G";
s[gi - 1][gj] = ".";
s[gi][gj - 1] = ".";
s[gi + 1][gj] = ".";
s[gi][gj + 1] = ".";
for (int i = 0; i < y; i++) {
for (int j = 0; j < x; j++) {
sb.append(s[i][j]);
}
sb.append("\n");
}
test("Z", sb.toString(), "I'm not sure.");
}

private static int randomInt(int min, int max) {
return min + (int) (((max + 1) - min) * Math.random());
}

private static String randomInt(String[] a) {
return a[(int) (a.length * Math.random())];
}

private static void test(String id, String input, String output) {
// System.out.format("%s\n", input.trim());
long start = System.nanoTime();
String result = run(input);
System.out.format("(%s)", output.equals(result) ? id : id
+ " expected:<" + output + "> but was:<" + result + ">");
double time = (System.nanoTime() - start) / 1e9;
System.out.format("[%.2f]\n", time);
if (!result.equals("-1") && time > 1) {
System.out.format("%s\n", input.trim());
System.exit(0);
}
}

private static String run(String input) {
Scanner sc = new Scanner(input);
int x = sc.nextInt();
int y = sc.nextInt();

int w = x;
int h = y;
int[][] map = new int[h][w];
int si = 0;
int sj = 0;
int gi = 0;
int gj = 0;
for (int i = 0; i < h; i++) {
String s = sc.next();
for (int j = 0; j < w; j++) {
char c = s.charAt(j);
if (c == '.') {
map[i][j] = -1;
} else if (c == 'S') {
si = i;
sj = j;
map[i][j] = -1;
} else if (c == 'G') {
gi = i;
gj = j;
map[i][j] = -1;
} else if (c == '#') {
map[i][j] = -2;
} else {
map[i][j] = -3;
}
}
}
String result = solve(h, w, si, sj, gi, gj, map);
sc.close();
return result;
}

private static void run() {
Scanner sc = new Scanner(System.in);
for (; sc.hasNext();) {
int x = sc.nextInt();
int y = sc.nextInt();
if (x == 0 && y == 0) {
break;
}

int w = x;
int h = y;
int[][] map = new int[h][w];
int si = 0;
int sj = 0;
int gi = 0;
int gj = 0;
for (int i = 0; i < h; i++) {
String s = sc.next();
for (int j = 0; j < w; j++) {
char c = s.charAt(j);
if (c == '.') {
map[i][j] = -1;
} else if (c == 'S') {
si = i;
sj = j;
map[i][j] = -1;
} else if (c == 'G') {
gi = i;
gj = j;
map[i][j] = -1;
} else if (c == '#') {
map[i][j] = -2;
} else {
map[i][j] = -3;
}
}
}
String result = solve(h, w, si, sj, gi, gj, map);
System.out.print(result + "\n");
}
sc.close();
}

private static String solve(int h, int w, int si, int sj, int gi, int gj,
int[][] map) {
return "" + breadthFirstSearch(h, w, si, sj, gi, gj, map);
}

private static class Data {
private int hash;
private int i;
private int j;
private int count;
private int[] ice;

public Data(int i, int j, int count, int[] ice) {
this.i = i;
this.j = j;
this.count = count;
this.ice = ice;
final int prime = 31;
int result = 1;
result = prime * result + i;
result = prime * result + j;
// result = prime * result + count;
// int c = 0;
// for (int k = 0; k < ice.length; k++) {
// c += ice[k];
// // result = prime * result + ice[k];
// }
// result = prime * result + c;
hash = result;
}

@Override
public int hashCode() {
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Data other = (Data) obj;
if (i != other.i)
return false;
if (j != other.j)
return false;
for (int k = 0; k < ice.length; k++) {
if (ice[k] < other.ice[k]) {
return false;
}
}
if (count < other.count)
return false;
return true;
}
}

private static int breadthFirstSearch(int h, int w, int si, int sj, int gi,
int gj, int[][] map) {
int count = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (map[i][j] == -3) {
depthFirstSearchIce(i, j, map, count);
count++;
}
}
}
int[] iceSize = new int[count];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (map[i][j] >= 0) {
iceSize[map[i][j]]++;
}
}
}
LinkedList<Data> list = new LinkedList<Data>();
HashSet<Data> used = new HashSet<Data>();
{
Data d = new Data(si, sj, 0, new int[iceSize.length]);
list.add(d);
used.add(d);
}

for (; !list.isEmpty();) {
Data d = list.poll();
if (d.i == gi && d.j == gj) {
return d.count;
}

for (int ni = 0; ni < next.length; ni++) {
int nexti = d.i + next[ni][0];
int nextj = d.j + next[ni][1];
if (nexti >= 0 && nexti < h && nextj >= 0 && nextj < w) {
int ii = map[nexti][nextj];
if (ii == -2
|| (ii >= 0 && d.ice[ii] + 1 > iceSize[ii] / 2)) {
continue;
}
int[] nextIce = Arrays.copyOf(d.ice, d.ice.length);
if (ii >= 0) {
nextIce[ii]++;
}
Data next = new Data(nexti, nextj, d.count + 1, nextIce);
if (!used.contains(next)) {
list.add(next);
used.add(next);
}
}
}
}
return -1;
}

private static final int[][] next = new int[][] { { -1, 0, }, { 0, -1, },
{ 0, 1, }, { 1, 0, }, };

private static void depthFirstSearchIce(int i, int j, int[][] map, int count) {
map[i][j] = count;
for (int ni = 0; ni < next.length; ni++) {
int nexti = i + next[ni][0];
int nextj = j + next[ni][1];
if (nexti >= 0 && nexti < map.length && nextj >= 0
&& nextj < map[nexti].length && map[nexti][nextj] == -3) {
depthFirstSearchIce(nexti, nextj, map, count);
}
}
}

}

problem AOJ 0246:   Bara-Bara Manju

how to solve Let m be the maximum of Bara-Bara Manju {b0,...,bn}. Then the maximum of Bara-Bara Manju {b0,...,bn,1,9} is m+1. This is trivial. Because, if the maximum is m+2, then there is bi, bj in {b0,...,bn} such that bi+1=10, bj+9=10. This means  bi + bj=10 and the maximum of Bara-Bara Manju {b0,...,bn} is m+1.
Similarly, the maximum of {b0,...,bn,2,8} is m+1, the maximum of {b0,...,bn,3,7} is m+1, the maximum of {b0,...,bn,4,6} is m+1 and the maximum of {b0,...,bn,5,5} is m+1.
From the above, I can cut down on the size of the problem.
After that, I use breadth-first search.

source code


import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;

public class BaraBaraManju {
private static boolean test = !true;

public static void main(String[] args) {
if (test) {
testA();
testB();
testC();
testD();
for (;;)
testZ();
} else {
run();
}
}

private static void testA() {
test("A", "5\n" + "4 9 1 3 8\n", "1");
}

private static void testB() {
test("B", "10\n" + "8 5 3 6 2 1 4 5 4 5\n", "4");
}

private static void testC() {
test("C", "9\n" + "5 7 3 8 2 9 6 4 1\n", "4");
}

private static void testD() {
StringBuilder sb = new StringBuilder();
int n = 100;
sb.append(n + "\n");
for (int i = 0; i < n; i++) {
sb.append("1 ");
}
sb.append("\n");
test("D", sb.toString(), "10");
}

private static void testZ() {
StringBuilder sb = new StringBuilder();
int n = 100;
sb.append(n + "\n");
int[] v = new int[] { 1, 2, 3, 4, };
for (int i = 0; i < n; i++) {
sb.append(randomInt(v) + " ");
}
sb.append("\n");
test("Z", sb.toString(), "I'm not sure.");
}

private static int randomInt(int min, int max) {
return min + (int) (((max + 1) - min) * Math.random());
}

private static int randomInt(int[] a) {
return a[(int) (a.length * Math.random())];
}

private static void test(String id, String input, String output) {
long start = System.nanoTime();
String result = run(input);
System.out.format("(%s)", output.equals(result) ? id : id
+ " expected:<" + output + "> but was:<" + result + ">");
double time = (System.nanoTime() - start) / 1e9;
System.out.format("[%.2f]\n", time);
if (time > 8) {
System.out.format("%s\n", input.trim());
}
}

private static String run(String input) {
Scanner sc = new Scanner(input);
int n = sc.nextInt();

int[] weight = new int[n];
for (int i = 0; i < weight.length; i++) {
weight[i] = sc.nextInt();
}
// String result = solve(n, weight);
String result2 = solve2(n, weight);
// if (!result.equals(result2)) {
// System.out.format("result=%s\nresult1=%s\n%s\n", result, result2,
// input);
// System.exit(0);
// }

sc.close();
return result2;
// return result;
}

private static void run() {
Scanner sc = new Scanner(System.in);
for (; sc.hasNext();) {
int n = sc.nextInt();
if (n == 0) {
break;
}

int[] weight = new int[n];
for (int i = 0; i < weight.length; i++) {
weight[i] = sc.nextInt();
}
String result = solve2(n, weight);
System.out.print(result + "\n");
}
sc.close();
}

private static String solve(int n, int[] weight) {
return "" + breadthFirstSearch(n, weight);
}

private static String solve2(int n, int[] weight) {
return "" + breadthFirstSearch2(n, weight);
}

private static class Data {
private int hash;
private int[] unused;
private int count;
private int sum;

public Data(int[] unused, int count, int sum) {
this.unused = unused;
this.count = count;
this.sum = sum;
final int prime = 31;
int result = 1;
result = prime * result + count;
result = prime * result + sum;
for (int i = 0; i < unused.length; i++) {
result = prime * result + unused[i];
}
hash = result;
}

@Override
public int hashCode() {
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Data other = (Data) obj;
if (count != other.count)
return false;
if (sum != other.sum)
return false;
for (int i = 0; i < unused.length; i++) {
if (unused[i] != other.unused[i]) {
return false;
}
}
return true;
}
}

private static int breadthFirstSearch(int n, int[] weight) {
LinkedList<Data> list = new LinkedList<Data>();
HashSet<Data> used = new HashSet<Data>();
{
int[] unused = new int[10];
for (int i = 0; i < n; i++) {
unused[weight[i]]++;
}
Data d = new Data(unused, 0, 0);
list.add(d);
used.add(d);
}

int max = 0;
for (; !list.isEmpty();) {
Data d = list.poll();
if (max < d.count) {
max = d.count;
}
for (int w = Math.min(10 - d.sum, 9); w >= 1; w--) {
if (d.unused[w] == 0) {
continue;
}
int nextSum = d.sum + w;
int nextCount = d.count;
if (nextSum == 10) {
nextCount++;
nextSum = 0;
}
int[] nextUnused = Arrays.copyOf(d.unused, 10);
nextUnused[w]--;
Data next = new Data(nextUnused, nextCount, nextSum);
if (!used.contains(next)) {
list.add(next);
used.add(next);
}
}
}
return max;
}

private static int breadthFirstSearch2(int n, int[] weight) {
LinkedList<Data> list = new LinkedList<Data>();
HashSet<Data> used = new HashSet<Data>();
{
int[] unused = new int[10];
for (int i = 0; i < n; i++) {
unused[weight[i]]++;
}
int count = 0;
for (int i = 1; i < 5; i++) {
int min = Math.min(unused[i], unused[10 - i]);
unused[i] -= min;
unused[10 - i] -= min;
count += min;
}
{
int min = unused[5] / 2;
unused[5] -= 2 * min;
count += min;
}
Data d = new Data(unused, count, 0);
list.add(d);
used.add(d);
}

int max = 0;
for (; !list.isEmpty();) {
Data d = list.poll();
if (max < d.count) {
max = d.count;
}
for (int w = Math.min(10 - d.sum, 9); w >= 1; w--) {
if (d.unused[w] == 0) {
continue;
}
int nextSum = d.sum + w;
int nextCount = d.count;
if (nextSum == 10) {
nextCount++;
nextSum = 0;
}
int[] nextUnused = Arrays.copyOf(d.unused, 10);
nextUnused[w]--;
Data next = new Data(nextUnused, nextCount, nextSum);
if (!used.contains(next)) {
list.add(next);
used.add(next);
}
}
}
return max;
}
}

problem AOJ 0245:   Time Sale

how to solve I use breadth-first search.

source code

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;

public class TimeSale {
private static boolean test = !true;

public static void main(String[] args) {
if (test) {
testA();
for (;;)
testZ();
} else {
run();
}
}

private static void testA() {
test("A",
"6 5\n" + "1 1 . 0 0 4\n" + "1 . . . . .\n" + ". . 2 2 . .\n"
+ ". . 2 2 3 3\n" + "P . . . . .\n" + "5\n"
+ "0 50 5 10\n" + "1 20 0 10\n" + "2 10 5 15\n"
+ "3 150 3 5\n" + "4 100 8 9\n", "180");
}

private static void testZ() {
StringBuilder sb = new StringBuilder();
int x = 20;
int y = 20;
sb.append(x + " " + y + "\n");
int sx = randomInt(0, x - 1);
int sy = randomInt(0, y - 1);
String[][] map = new String[y][x];
for (int i = 0; i < y; i++) {
for (int j = 0; j < x; j++) {
if (i % 2 == 0 || j % 2 == 0) {
map[i][j] = ".";
} else {
int r = randomInt(0, 9);
map[i][j] = "" + r;
}
}
}
map[sy][sx] = "P";
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
sb.append(map[i][j] + " ");
}
sb.append("\n");
}

int n = randomInt(1, 8);
sb.append(n + "\n");
int get = 0;
for (int i = 0; i < n; i++) {
int g = randomInt(0, 9);
while ((get & (1 << g)) != 0) {
g = randomInt(0, 9);
}
get |= (1 << g);
int s = randomInt(0, 100);
int e = randomInt(0, 100);
if (s > e) {
int t = s;
s = e;
e = t;
}
sb.append(g + " " + (randomInt(1, 20) * 10) + " " + s + " " + e
+ "\n");
}
test("Z", sb.toString(), "I'm not sure.");
}

private static int randomInt(int min, int max) {
return min + (int) (((max + 1) - min) * Math.random());
}

private static void test(String id, String input, String output) {
long start = System.nanoTime();
String result = run(input);
System.out.format("(%s)", output.equals(result) ? id : id
+ " expected:<" + output + "> but was:<" + result + ">");
double time = (System.nanoTime() - start) / 1e9;
System.out.format("[%.2f]\n", time);
if (time > 5) {
System.out.format("%s\n", input.trim());
}
}

private static String run(String input) {
Scanner sc = new Scanner(input);
int x = sc.nextInt();
int y = sc.nextInt();

int sx = 0;
int sy = 0;
int[][] map = new int[y][x];
for (int i = 0; i < y; i++) {
for (int j = 0; j < x; j++) {
String next = sc.next();
if (next.equals(".")) {
map[i][j] = -1;
} else if (next.equals("P")) {
sx = j;
sy = i;
map[i][j] = -1;
} else {
map[i][j] = Integer.parseInt(next);
}
}
}

int n = sc.nextInt();
int[][] sale = new int[n][4];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 4; j++) {
sale[i][j] = sc.nextInt();
}
}

String result = solve(x, y, sx, sy, map, sale);
sc.close();
return result;
}

private static void run() {
Scanner sc = new Scanner(System.in);
for (; sc.hasNext();) {
int x = sc.nextInt();
int y = sc.nextInt();
if (x == 0 && y == 0) {
break;
}

int sx = 0;
int sy = 0;
int[][] map = new int[y][x];
for (int i = 0; i < y; i++) {
for (int j = 0; j < x; j++) {
String next = sc.next();
if (next.equals(".")) {
map[i][j] = -1;
} else if (next.equals("P")) {
sx = j;
sy = i;
map[i][j] = -1;
} else {
map[i][j] = Integer.parseInt(next);
}
}
}

int n = sc.nextInt();
int[][] sale = new int[n][4];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 4; j++) {
sale[i][j] = sc.nextInt();
}
}

String result = solve(x, y, sx, sy, map, sale);
System.out.print(result + "\n");
}
sc.close();
}

private static String solve(int x, int y, int sx, int sy, int[][] map,
int[][] sale) {
return "" + breadthFirstSearch(x, y, sx, sy, map, sale);
}

private static class Data {
private int hash;
private int x;
private int y;
private int time;
private int discount;
private int get;

public Data(int time, int x, int y, int discount, int get) {
this.x = x;
this.y = y;
this.time = time;
this.discount = discount;
this.get = get;
final int prime = 31;
int result = 1;
result = prime * result + time;
result = prime * result + x;
result = prime * result + y;
result = prime * result + discount;
result = prime * result + get;
hash = result;
}

@Override
public int hashCode() {
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Data other = (Data) obj;
if (time != other.time)
return false;
if (x != other.x)
return false;
if (y != other.y)
return false;
if (get != other.get)
return false;
if (discount != other.discount)
return false;
return true;
}

}

private static final int[][] next = new int[][] { { -1, 0, }, { 0, -1, },
{ 0, 1, }, { 1, 0, }, };

private static int breadthFirstSearch(int x, int y, int sx, int sy,
int[][] map, int[][] sale) {
LinkedList<Data> list = new LinkedList<Data>();
HashSet<Data> used = new HashSet<Data>();
{
Data d = new Data(0, sx, sy, 0, 0);
list.add(d);
used.add(d);
}

int max = 0;
for (; !list.isEmpty();) {
Data d = list.poll();
for (int i = 0; i < next.length; i++) {
int nexti = d.y + next[i][0];
int nextj = d.x + next[i][1];
if ((nexti >= 0 && nexti < y) && (nextj >= 0 && nextj < x)) {
} else {
continue;
}
if (map[nexti][nextj] != -1
&& (d.get & (1 << map[nexti][nextj])) == 0) {
for (int si = 0; si < sale.length; si++) {
if (map[nexti][nextj] == sale[si][0]
&& d.time >= sale[si][2]
&& d.time < sale[si][3]) {
d.discount += sale[si][1];
d.get |= (1 << map[nexti][nextj]);
}
}
}
}

max = Math.max(max, d.discount);

for (int i = 0; i < next.length; i++) {
int nexti = d.y + next[i][0];
int nextj = d.x + next[i][1];
int nextTime = d.time + 1;
if ((nexti >= 0 && nexti < y) && (nextj >= 0 && nextj < x)
&& map[nexti][nextj] == -1 && nextTime < 100) {
} else {
continue;
}

Data next = new Data(nextTime, nextj, nexti, d.discount, d.get);
if (!used.contains(next)) {
list.add(next);
used.add(next);
}
}
}
return max;
}
}

problem AOJ 0244:   Hot Spring Trip

how to solve I use priority-first search.

source code

import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class HotSpringTrip {
private static class Data implements Comparable<Data> {
private int hash;
private int current;
private int cost;
private boolean hasTicket;

public Data(int current, int cost, boolean hasTicket) {
this.current = current;
this.cost = cost;
this.hasTicket = hasTicket;
final int prime = 31;
int result = 1;
// result = prime * result + cost;
result = prime * result + current;
result = prime * result + (hasTicket ? 1231 : 1237);
hash = result;
}

@Override
public int hashCode() {
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Data other = (Data) obj;
// if (cost != other.cost)
// return false;
if (cost < other.cost)
return false;
if (current != other.current)
return false;
if (hasTicket != other.hasTicket)
return false;
return true;
}

@Override
public int compareTo(Data o) {
if (cost < o.cost) {
return -1;
}
if (cost > o.cost) {
return 1;
}
return 0;
}

}

private static boolean test = !true;

public static void main(String[] args) {
if (test) {
testA();
testB();
testC();
for (;;)
testZ();
} else {
run();
}
}

private static void testA() {
test("A", "2 1\n" + "1 2 5\n", "5");
}

private static void testB() {
test("B", "3 2\n" + "1 2 5\n" + "2 3 5\n", "0");
}

private static void testC() {
test("C", "6 9\n" + "1 2 7\n" + "1 3 9\n" + "1 5 14\n" + "2 3 10\n"
+ "2 4 15\n" + "3 4 11\n" + "3 5 2\n" + "4 5 9\n" + "4 6 8\n",
"7");
}

private static void testZ() {
StringBuilder sb = new StringBuilder();
int n = 100;
int m = randomInt(1, ((n * n) - n) / 2);
sb.append(n + " " + m + "\n");
int[][] map = new int[n][n];
for (int k = 0; k < m; k++) {
int i = randomInt(1, n);
int j = randomInt(1, n);
int c = randomInt(1, 1000);
while (map[i - 1][j - 1] != 0) {
i = randomInt(1, n);
j = randomInt(1, n);
c = randomInt(1, 1000);
}
map[i - 1][j - 1] = c;
sb.append(i + " " + j + " " + c + "\n");
}
test("Z", sb.toString(), "I'm not sure.");
}

private static int randomInt(int min, int max) {
return min + (int) (((max + 1) - min) * Math.random());
}

private static void test(String id, String input, String output) {
long start = System.nanoTime();
String result = run(input);
System.out.format("(%s)", output.equals(result) ? id : id
+ " expected:<" + output + "> but was:<" + result + ">");
double time = (System.nanoTime() - start) / 1e9;
System.out.format("[%.2f]\n", time);
if (time > 1) {
System.out.format("%s\n", input.trim());
}
}

private static String run(String input) {
Scanner sc = new Scanner(input);
int n = sc.nextInt();
int m = sc.nextInt();

int[][] map = new int[n][n];
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
map[i][j] = Integer.MAX_VALUE;
}
}
for (int i = 0; i < m; i++) {
int from = sc.nextInt() - 1;
int to = sc.nextInt() - 1;
int cost = sc.nextInt();
map[from][to] = cost;
map[to][from] = cost;
}
// String result = solve(n, m, map);
String resultPfs = solvePfs(n, m, map);
// if (!result.equals(resultPfs)) {
// System.out.format("result=%s\nresult1=%s\n%s\n", result, resultPfs,
// input);
// System.exit(0);
// }

sc.close();
return resultPfs;
// return result;
}

private static void run() {
Scanner sc = new Scanner(System.in);
for (; sc.hasNext();) {
int n = sc.nextInt();
int m = sc.nextInt();
if (n == 0 && m == 0) {
break;
}

int[][] map = new int[n][n];
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
map[i][j] = Integer.MAX_VALUE;
}
}
for (int i = 0; i < m; i++) {
int from = sc.nextInt() - 1;
int to = sc.nextInt() - 1;
int cost = sc.nextInt();
map[from][to] = cost;
map[to][from] = cost;
}
String result = solvePfs(n, m, map);
System.out.print(result + "\n");
}
sc.close();
}

private static String solve(int n, int m, int[][] map) {
return "" + breadthFirstSearch(n, m, map);
}

private static String solvePfs(int n, int m, int[][] map) {
return "" + priorityFirstSearch(n, m, map);
}

private static int breadthFirstSearch(int n, int m, int[][] map) {
LinkedList<Data> list = new LinkedList<Data>();
HashSet<Data> used = new HashSet<Data>();
{
Data d = new Data(0, 0, true);
list.add(d);
used.add(d);
}

int min = Integer.MAX_VALUE;
for (; !list.isEmpty();) {
Data d = list.poll();

if (d.cost > min) {
continue;
}
if (d.current == n - 1) {
min = Math.min(min, d.cost);
}

for (int i = 0; i < n; i++) {
if (map[d.current][i] == Integer.MAX_VALUE) {
continue;
}
int nextCurrent = i;
{
int nextCost = d.cost + map[d.current][i];
Data next = new Data(nextCurrent, nextCost, d.hasTicket);
if (!used.contains(next)) {
list.add(next);
used.add(next);
}
}
if (d.hasTicket) {
for (int j = 0; j < n; j++) {
if (map[nextCurrent][j] == Integer.MAX_VALUE) {
continue;
}
Data next = new Data(j, d.cost, false);
if (!used.contains(next)) {
list.add(next);
used.add(next);
}
}
}
}
}
return min;
}

private static int priorityFirstSearch(int n, int m, int[][] map) {
PriorityQueue<Data> list = new PriorityQueue<Data>();
HashSet<Data> used = new HashSet<Data>();
{
Data d = new Data(0, 0, true);
list.add(d);
used.add(d);
}

for (; !list.isEmpty();) {
Data d = list.poll();

if (d.current == n - 1) {
return d.cost;
}

for (int i = 0; i < n; i++) {
if (map[d.current][i] == Integer.MAX_VALUE) {
continue;
}
int nextCurrent = i;
{
int nextCost = d.cost + map[d.current][i];
Data next = new Data(nextCurrent, nextCost, d.hasTicket);
if (!used.contains(next)) {
list.add(next);
used.add(next);
}
}
if (d.hasTicket) {
for (int j = 0; j < n; j++) {
if (map[nextCurrent][j] == Integer.MAX_VALUE) {
continue;
}
Data next = new Data(j, d.cost, false);
if (!used.contains(next)) {
list.add(next);
used.add(next);
}
}
}
}
}
return Integer.MAX_VALUE;
}
}


source code

/*
* Chapter 24. Elementary Geometric Methods - Problem 7 - Robert Sedgewick Algorithms in C++
* 同一の線分2本を与えたとき、関数intersectが返す値は何か?
*/
import java.util.Scanner;

public class Chapter24ElementaryGeometricMethodsProblem7 {
public static void main(String[] args) {
testA();
for (;;)
testZ();
}

private static void testA() {
test("A", "0 0\n" + "1 1\n", "true");
}

private static void testZ() {
StringBuilder sb = new StringBuilder();
int x0 = randomInt(1, 100);
int y0 = randomInt(1, 100);
int x1 = randomInt(1, 100);
int y1 = randomInt(1, 100);
sb.append(x0 + " " + y0 + " " + x1 + " " + y1 + " " + "\n");
test("Z", sb.toString(), "true");
}

private static int randomInt(int min, int max) {
return min + (int) (((max + 1) - min) * Math.random());
}

private static void test(String id, String input, String output) {
System.out.format("%s\n", input.trim());
long start = System.nanoTime();
String result = run(input);
System.out.format("(%s)", output.equals(result) ? id : id
+ " expected:<" + output + "> but was:<" + result + ">");
double time = (System.nanoTime() - start) / 1e9;
System.out.format("[%.2f]\n", time);
}

private static String run(String input) {
Scanner sc = new Scanner(input);
int x0 = sc.nextInt();
int y0 = sc.nextInt();
int x1 = sc.nextInt();
int y1 = sc.nextInt();
Line l1 = new Line(new Point(x0, y0), new Point(x1, y1));
Line l2 = new Line(new Point(x0, y0), new Point(x1, y1));

String result = "" + intersect(l1, l2);

sc.close();
return result;
}

/**
* Cartesian coordinate system
*/
private static class Point {
private int x;
private int y;

public Point(int x, int y) {
this.x = x;
this.y = y;
}
}

private static class Line {
private Point p1;
private Point p2;

public Line(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
}

private static boolean intersect(Line l1, Line l2) {
return (ccw(l1.p1, l1.p2, l2.p1) * ccw(l1.p1, l1.p2, l2.p2) <= 0)
&& (ccw(l2.p1, l2.p2, l1.p1) * ccw(l2.p1, l2.p2, l1.p2) <= 0);
}

private static int ccw(Point p0, Point p1, Point p2) {
return ccw(p0.x, p0.y, p1.x, p1.y, p2.x, p2.y);
}

private static int ccw(int x0, int y0, int x1, int y1, int x2, int y2) {
int dx1 = x1 - x0;
int dy1 = y1 - y0;
int dx2 = x2 - x0;
int dy2 = y2 - y0;
if (dx1 * dy2 > dy1 * dx2) {
return 1;
}
if (dx1 * dy2 < dy1 * dx2) {
return -1;
}
if ((dx1 * dx2 < 0) || (dy1 * dy2 < 0)) {
return -1;
}
if ((dx1 * dx1 + dy1 * dy1) < (dx2 * dx2 + dy2 * dy2)) {
return 1;
}
return 0;
}
}

このページのトップヘ