Register
|
Login
Home
News
Competitions
Practice
How to
Rankings
Calendar
Arena
CodeFu 2010
CodeFu'10 Highlights
Jazoon'10 Highlights
Schedule
Rules
Prizes
Results
Competitions
»
Main CodeFu Competitons
»
CodeFu 2010
»
Results
CodeFu 2010 Results
Final Round Results
toroman's solution for 400: GivesYouWings, written in Java, submitted on 09.05.2010 14:05:33
import java.util.ArrayDeque; import java.util.Arrays; import java.util.Comparator; public class GivesYouWings { ArrayDeque<int[]> q = new ArrayDeque<int[]>(1000); boolean[] enqued = new boolean[1000]; private int ilen; private int jlen; private String[] maze; int[][] mods = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } }; private static GivesYouWings wings; public int solve(String[] maze) { ilen = maze.length; jlen = maze[0].length(); this.maze = maze; // find bulls and st int si, sj, ei, ej; si = sj = ei = ej = -1; int rb = 0; for (int i = 0; i < ilen; i++) for (int j = 0; j < jlen; j++) switch (maze[i].charAt(j)) { case '*': rb++; break; case 'S': si = i; sj = j; break; case 'T': ei = i; ej = j; break; } int best = distance(si, sj, ei, ej); if (best == Integer.MAX_VALUE) { return -1; } else { best *= 256; } int[][] bull = new int[rb][4]; rb = 0; for (int i = 0; i < ilen; i++) for (int j = 0; j < jlen; j++) if (maze[i].charAt(j) == '*') { bull[rb][2] = distance(si, sj, i, j); bull[rb][3] = distance(i, j, ei, ej); if (bull[rb][2] == Integer.MAX_VALUE || bull[rb][3] == Integer.MAX_VALUE) { continue; } bull[rb][0] = i; bull[rb][1] = j; rb++; } bull = Arrays.copyOf(bull, rb); int[][] bdist = new int[rb][rb]; for (int i = 0; i < rb; i++) { bdist[i][i] = 0; for (int j = i + 1; j < rb; j++) { bdist[i][j] = bdist[j][i] = distance(bull[i][0], bull[i][1], bull[j][0], bull[j][1]); } } int highmask = 1 << rb; Arrays.sort(bull, new Comparator<int[]>() { public int compare(int[] rb1, int[] rb2) { return rb1[2] - rb2[2]; } }); boolean[] vis = new boolean[10]; int[] todo = new int[10]; Mask: for (int mask = 1; mask < highmask; mask++) { Arrays.fill(vis, false); int tix = 0; for (int i = 0; i < 8; i++) { if ((mask & (1 << i)) != 0) { todo[tix++] = i; } } int prevb = todo[0]; int rez = 0; // find closest for (int i = 1; i < tix; i++) { if (bull[todo[i]][2] < bull[prevb][2]) { prevb = todo[i]; } } if (bull[prevb][2] == Integer.MAX_VALUE) { continue; } // continue path vis[prevb] = true; rez += bull[prevb][2] * 256; for (int j = 1; j < tix; j++) { int speed = 256 >>> j; int nextbv = Integer.MAX_VALUE; int nextbi = -1; for (int i = 0; i < tix; i++) { if (vis[todo[i]]) continue; if (bdist[prevb][todo[i]] < nextbv) { nextbv = bdist[prevb][todo[i]]; nextbi = todo[i]; } } if (nextbv == Integer.MAX_VALUE) { continue Mask; } vis[nextbi] = true; rez += nextbv * speed; prevb = nextbi; } rez += bull[prevb][3] * (256 >>> tix); best = Math.min(best, rez); } return best; } int distance(int si, int sj, int ei, int ej) { Arrays.fill(enqued, false); q.clear(); q.push(new int[] { si, sj, 0 }); enqued[si * 32 + sj] = true; while (!q.isEmpty()) { int[] nod = q.removeFirst(); for (int[] mod : mods) { int ni = nod[0] + mod[0]; int nj = nod[1] + mod[1]; // if (ni == 0 && nj == 1) { // System.out.println("Preth."); // } if (ni >= ilen || ni < 0 || nj >= jlen || nj < 0) { continue; } if (maze[ni].charAt(nj) == '#') { continue; } if (enqued[ni * 32 + nj]) { continue; } if (ni == ei && nj == ej) { return nod[2] + 1; } enqued[ni * 32 + nj] = true; q.addLast(new int[] { ni, nj, nod[2] + 1 }); } } return Integer.MAX_VALUE; } public static void main(String[] args) { wings = new GivesYouWings(); String[] c = { "S..........", ".#.#####...", ".#.........", ".#.###.###.", ".#.#.#.....", ".#T#.#.#*#.", "..........." }; System.out.println(wings.solve(c)); System.out.println("Expected 1792"); } }