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

	}

}