Competitions » Main CodeFu Competitons » CodeFu 2010 » Results
CodeFu 2010 Results

Final Round Results

BojanKostadinov's solution for 400: GivesYouWings, written in Java, submitted on 09.05.2010 13:19:22

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class GivesYouWings {
	public int solve(String[] maze) {
		int startx = 0, starty = 0, endx = 0, endy = 0;
		HashMap<Integer, Integer> bullPosition = new HashMap<Integer, Integer>();

		int position = 0;

		for (int i = 0; i < maze.length; i++)
			for (int j = 0; j < maze[0].length(); j++) {
				if (maze[i].charAt(j) == 'S') {
					startx = i;
					starty = j;
				}

				if (maze[i].charAt(j) == 'T') {
					endx = i;
					endy = j;
				}

				if (maze[i].charAt(j) == '*') {
					bullPosition.put(i * 100 + j, position);
					position++;
				}
			}

		// System.out.println(startx + " " + starty);
		// System.out.println(endx + " " + endy);

		int dx[] = new int[] { -1, 0, 1, 0 };
		int dy[] = new int[] { 0, -1, 0, 1 };

		Queue<Position> q = new LinkedList<Position>();
		q.add(new Position(startx, starty, 0, 0));
		int total = 0;

		int best[][][] = new int[40][40][500];

		for (int i = 0; i < 40; i++)
			for (int j = 0; j < 40; j++)
				for (int k = 0; k < 500; k++)
					best[i][j][k] = Integer.MAX_VALUE;

		best[startx][starty][0] = 0;

		while (q.size() > 0 && total++ < 1000000) {
			Position c = q.poll();
			int speed = 256;

			// System.out.println(c.x + " " + c.y + " " + c.takenBulls);

			int o = Integer.bitCount(c.takenBulls);

			for (int z = 0; z < o; z++)
				speed /= 2;

			for (int i = 0; i < dx.length; i++) {
				int nx = c.x + dx[i];
				int ny = c.y + dy[i];
				Position n = new Position(0, 0, 0, 0);
				n.x = c.x;
				n.y = c.y;
				n.takenBulls = c.takenBulls;

				if (nx < 0 || nx >= maze.length)
					continue;
				if (ny < 0 || ny >= maze[0].length())
					continue;

				if (maze[nx].charAt(ny) == '*') {
					int z = 1 << bullPosition.get(nx * 100 + ny);

					if ((z & n.takenBulls) <= 0) {
						// take bull
						n.takenBulls += z;
					}
				}

				n.x = nx;
				n.y = ny;
				n.time = c.time + speed;

				// System.out.println("- " + n.x + " " + n.y + " " + n.time);

				if (maze[n.x].charAt(n.y) != '#') {

					// System.out.println(best[nx][ny][n.takenBulls]);
					// System.out.println(best[c.x][c.y][c.takenBulls]);
					if (best[nx][ny][n.takenBulls] > best[c.x][c.y][c.takenBulls]
							+ speed) {
						best[nx][ny][n.takenBulls] = best[c.x][c.y][c.takenBulls]
								+ speed;
						q.add(n);
					}
				}
			}

		}

		int smallest = Integer.MAX_VALUE;

		for (int i = 0; i < 300; i++)
			if (best[endx][endy][i] < smallest) {
				smallest = best[endx][endy][i];
			}

		if (smallest == Integer.MAX_VALUE)
			return -1;

		return smallest;
	}

	/*
	public static void main(String[] args) {

		GivesYouWings object = new GivesYouWings();
//
//		System.out.println(object.solve(new String[] { "S...*.....",
//				"*.........", "....*.....", ".........*", ".*........",
//				"..........", "..........", "..........", "..........",
//				"......***T" }));
	}
	*/
}

final class Position {
	public int x, y, time;
	public int takenBulls = 0;

	public Position(int x, int y, int time, int takenBulls) {
		this.x = x;
		this.y = y;
		this.time = time;
		this.takenBulls = takenBulls;
	}

}