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
time_bandit's solution for 400: GivesYouWings, written in Java, submitted on 09.05.2010 14:10:55
import java.awt.Point; import java.util.LinkedList; import java.util.Queue; public class GivesYouWings { public int solve(String[] maze) { int x = 0, y = 0; int result = -1; int curspeed = 256; Queue<Point> q = new LinkedList<Point>(); int n = 0; int[][] vreme = new int[maze.length][maze[0].length()]; for (int i = 0; i < vreme.length; i++) { for (int j = 0; j < vreme[0].length; j++) { vreme[i][j] = Integer.MAX_VALUE; if (maze[i].charAt(j) == 'S') { vreme[i][j] = 0; q.add(new Point(i, j)); } if (maze[i].charAt(j) == 'T') { x = i; y = j; } if (maze[i].charAt(j) == '*') n++; } } Point[] redbull = new Point[n]; int brojac = 0; int[] di = { 1, 0, -1, 0 }; int[] dj = { 0, 1, 0, -1 }; int[] redbulivreme = new int[n]; n = 0; while (!q.isEmpty()) { Point tmp = new Point(q.poll()); if (maze[tmp.x].charAt(tmp.y) == '*') { redbull[n++] = new Point(tmp); redbulivreme[brojac++] = vreme[tmp.x][tmp.y]; } // System.out.println(tmp); for (int i = 0; i < dj.length; i++) { int ii = tmp.x; int jj = tmp.y; ii += di[i]; jj += dj[i]; if (ii < maze.length && ii > -1 && jj < maze[0].length() && jj > -1) { if (maze[ii].charAt(jj) != '#') { if (vreme[ii][jj] > curspeed + vreme[tmp.x][tmp.y]) { vreme[ii][jj] = (curspeed + vreme[tmp.x][tmp.y]); q.add(new Point(ii, jj)); } } } } } result = Integer.MAX_VALUE; if (result > vreme[x][y]) result = vreme[x][y]; result = vreme[x][y]; for (int i = 0; i < redbull.length; i++) { curspeed /= 2; for (int k = 0; k < vreme.length; k++) { for (int k2 = 0; k2 < vreme[0].length; k2++) { vreme[k][k2] = Integer.MAX_VALUE; if (k == redbull[i].x && k2 == redbull[i].y) { q.add(new Point(redbull[i])); vreme[k][k2] = redbulivreme[i]; } } } brojac = i; while (!q.isEmpty()) { Point tmp = new Point(q.poll()); if (maze[tmp.x].charAt(tmp.y) == '*') { if (redbulivreme[brojac] > vreme[tmp.x][tmp.y]) redbulivreme[brojac] = vreme[tmp.x][tmp.y]; } // System.out.println(tmp); for (int a = 0; a < dj.length; a++) { int ii = tmp.x; int jj = tmp.y; ii += di[a]; jj += dj[a]; if (ii < maze.length && ii > -1 && jj < maze[0].length() && jj > -1) { if (maze[ii].charAt(jj) != '#') { if (vreme[ii][jj] > curspeed + vreme[tmp.x][tmp.y]) { vreme[ii][jj] = (curspeed + vreme[tmp.x][tmp.y]); q.add(new Point(ii, jj)); } } } } } if (result > vreme[x][y]) result = vreme[x][y]; } if (result == Integer.MAX_VALUE) return -1; return result; } /** * @param args */ public static void main(String[] args) { System.out.println(new GivesYouWings().solve(new String[] { "#######", "#T....#", "####.*#", "#...S.#", "#######" })); // TODO Auto-generated method stub } }