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
Ilija139's solution for 400: GivesYouWings, written in Java, submitted on 09.05.2010 13:32:11
import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; public class GivesYouWings { public static int solve(String[] maze) { int maxTime = 512; char[][][] map = new char[30][30][maxTime]; int initI = 0, initJ = 0; int targetI = 0, targetJ = 0; for (int j = 0; j < maze.length; ++j) { for (int i = 0; i < maze[j].length(); ++i) { char c = maze[j].charAt(i); if (c == 'S') { initI = i; initJ = j; } if (c == 'T') { targetI = i; targetJ = j; } map[i][j][0] = maze[j].charAt(i); } } for (int j = 0; j < maze.length; ++j) { for (int i = 0; i < maze[j].length(); ++i) { System.out.print(map[i][j][0]); } System.out.println(); } int timeStep = 1; long timeNeeded = 0; int redBulls = 0; int speed = (int) Math.pow(2, 8 - redBulls); int maxI = maze[0].length(); int maxJ = maze.length; int maxMoves = 0; String[] moves = new String[4]; int ii = initI, jj = initJ; // char c = map[ii][jj][0]; if (ii + 1 < maxI) { // can go right if (map[ii + 1][jj][0] != '#') { // its not wall // go right map[ii + 1][jj][1] = (char) getSpeed(redBulls); moves[maxMoves] = (ii + 1) + " " + jj; ++maxMoves; int d = map[ii + 1][jj][1]; } } if (ii - 1 > 0) { // can go left if (map[ii - 1][jj][0] != '#') { // its not wall // go left map[ii - 1][jj][1] = (char) getSpeed(redBulls); moves[maxMoves] = (ii - 1) + " " + jj; ++maxMoves; int d = map[ii - 1][jj][1]; } } if (jj + 1 < maxJ) { // can go down if (map[ii][jj + 1][0] != '#') { // its not wall // go down map[ii][jj + 1][1] = (char) getSpeed(redBulls); moves[maxMoves] = ii + " " + (jj + 1); ++maxMoves; int d = map[ii][jj + 1][1]; } } if (jj - 1 > 0) { // can go right if (map[ii][jj - 1][0] != '#') { // its not wall // go right map[ii][jj - 1][1] = (char) getSpeed(redBulls); moves[maxMoves] = (ii) + " " + (jj - 1); ++maxMoves; int d = map[ii][jj - 1][1]; } } List<Integer> arr = new ArrayList<Integer>(); int[][] speeds = new int[30][30]; for (int i = 0; i < 30; ++i) { Arrays.fill(speeds[i], 256); } for (int time = 1; time < maxTime - 1; ++time) { for (int j = 0; j < maxJ; ++j) { for (int i = 0; i < maxI; ++i) { char c = map[i][j][time]; if (c == 0) { continue; } int s = map[i][j][time]; if(i==3&&j==1){ System.out.println(s); } if(i==5 && j ==1){ System.out.println(speeds[i][j]); } if (map[i][j][0] == '*') { map[i][j][0] = '.'; speeds[i][j] /= 2; } int t = speeds[i][j]; if(t==128){ System.out.println("ss"); } int currentSpeed = s + speeds[i][j]; if (i == targetI && j == targetJ) { arr.add(s); } if (i + 1 < maxI) { // can go right if (map[i + 1][j][0] != '#') { // its not wall // go right int oldSpeed = map[i + 1][j][time+1]; int speedNext = currentSpeed; speeds[i+1][j]=Math.min(speeds[i][j],speeds[i+1][j]); if (oldSpeed != 0) { speedNext = (int) Math.min(currentSpeed, oldSpeed); } map[i + 1][j][time + 1] = (char) speedNext; int d = map[i + 1][j][time]; } } if (i - 1 > 0) { // can go left if (map[i - 1][j][0] != '#') { // its not wall // go left speeds[i-1][j]=Math.min(speeds[i][j],speeds[i-1][j]); int oldSpeed = map[i - 1][j][time+1]; int speedNext = currentSpeed; if (oldSpeed != 0) { speedNext = (int) Math.min(currentSpeed, oldSpeed); } map[i - 1][j][time + 1] = (char) speedNext; int d = map[i - 1][j][1]; } } if (j + 1 < maxJ) { // can go down if (map[i][j + 1][0] != '#') { // its not wall // go down int oldSpeed = map[i][j + 1][time+1]; int speedNext = currentSpeed; speeds[i][j+1]=Math.min(speeds[i][j],speeds[i][j+1]); if (oldSpeed != 0) { speedNext = (int) Math.min(currentSpeed, oldSpeed); } map[i][j + 1][time + 1] = (char) speedNext; int d = map[i][j + 1][1]; } } if (j - 1 > 0) { // can go up if (map[i][j - 1][0] != '#') { // its not wall // go right int oldSpeed = map[i][j - 1][time+1]; int speedNext = currentSpeed; speeds[i][j-1]=Math.min(speeds[i][j],speeds[i][j-1]); if (oldSpeed != 0) { speedNext = (int) Math.min(currentSpeed, oldSpeed); } map[i][j - 1][time + 1] = (char) speedNext; int d = map[i][j - 1][1]; } } } } } int min = Integer.MAX_VALUE; for (int i = 1; i < maxTime; ++i) { int tek = map[targetI][targetJ][i]; if (tek != 0 && tek < min) { min = tek; } } Collections.sort(arr); if(arr.size() == 0)return -1; else return arr.get(0); } private class Place { int i; int j; public Place(int i, int j) { this.i = i; this.j = j; } } public static int getSpeed(int redBulls) { return (int) Math.pow(2, 8 - redBulls); } public static void main(String[] args) { String[] maze = { "#######", "#T....#", "####.*#", "#...S.#", "#######" }; System.out.println("AA"+solve(maze)); } }