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
igorkulev's solution for 400: GivesYouWings, written in Java, submitted on 09.05.2010 13:16:35
import java.util.LinkedList; import java.util.Queue; public class GivesYouWings { public static void main(String[] args) { int answer = new GivesYouWings().solve(new String[]{".....####","######..#","#S..*...#","#######T#","......###"}); System.out.println(answer); } char m[][]; int M; int N; int sy, sx, ey, ex; int rby[]; int rbx[]; int T; int TOrder; int test; int opt[][][][]; int best; int order[]; boolean taken[]; void printMatrix() { int i,j,k; } void printPath() { System.out.println("START:"); int i; for (i=0;i<TOrder;i++) { System.out.println("TAKEN: "+order[i]); } System.out.println("END:"); } void calculate() { int i,j,k; //test++; //printPath(); // we go from S, then we move to the red bull places, in the end we come back to T int momy = sy; int momx = sx; //System.out.println("MOM: "+momy+" "+momx); int res = 0; int pathvalue = 256; for (i=0;i<TOrder;i++) { res += (opt[momy][momx][rby[order[i]]][rbx[order[i]]]*pathvalue); //System.out.println("MOM: "+momy+" "+momx); momy = rby[order[i]]; momx = rbx[order[i]]; // we have taken red bull, we decrease pathvalue pathvalue /= 2; } // the ending point res += (opt[momy][momx][ey][ex]*pathvalue); best = Math.min(best, res); } void recurse(int level) { int i,j,k; // we are sure that there will be max level red bulls after executing this code //System.out.println("LEVEL: "+level); // i try with this path calculate(); for (i=0;i<T;i++) { if (taken[i] == false) { taken[i] = true; //System.out.println("LA: "+i); // we put this in order order[level] = i; TOrder = level+1; recurse(level+1); taken[i] = false; } } } boolean isMovable(char c) { if (c == '.') return true; if (c == '*') return true; if (c == 'S') return true; if (c == 'T') return true; return false; } public int solve(String[] maze) { int i,j,k; M = maze.length; N = maze[0].length(); m = new char[M+2][N+2]; rby = new int[8]; rbx = new int[8]; taken = new boolean[8]; order = new int[8]; for (i=0;i<=M+1;i++) { for (j=0;j<=N+1;j++) { m[i][j] = '#'; } } T = 0; for (i=0;i<M;i++) { for (j=0;j<N;j++) { m[i+1][j+1] = maze[i].charAt(j); if (m[i+1][j+1] == '*') { // there is red bull here rby[T] = i+1; rbx[T] = j+1; T++; } if (m[i+1][j+1] == 'S') { // the starting position sy = i+1; sx = j+1; } if (m[i+1][j+1] == 'T') { // the starting position ey = i+1; ex = j+1; } } } //System.out.println("TEST: "+test); // we calculate the path in normal distance between each two vertices Queue<Integer> qy = new LinkedList<Integer>(); Queue<Integer> qx = new LinkedList<Integer>(); int fromy, fromx; int toy, tox; int ty, tx; int dy[] = {-1, 0, 1, 0}; int dx[] = {0, 1, 0, -1}; int newy, newx; opt = new int[M+2][N+2][M+2][N+2]; for (fromy = 1;fromy<=M;fromy++) { for (fromx = 1;fromx<=N;fromx++) { for (toy = 1;toy<=M;toy++) { for (tox = 1;tox<=N;tox++) { opt[fromy][fromx][toy][tox] = -1; } } } } for (fromy = 1;fromy<=M;fromy++) { for (fromx = 1;fromx<=N;fromx++) { if (isMovable(m[fromy][fromx]) == false) continue; // we make BFS from here opt[fromy][fromx][fromy][fromx] = 0; qy.add(fromy); qx.add(fromx); while (qy.isEmpty() == false) { // we take the last element ty = qy.poll(); tx = qx.poll(); for (k=0;k<4;k++) { newy = ty+dy[k]; newx = tx+dx[k]; if (isMovable(m[newy][newx]) == true) { // if we haven't been here if (opt[fromy][fromx][newy][newx] == -1) { opt[fromy][fromx][newy][newx] = opt[fromy][fromx][ty][tx]+1; qy.add(newy); qx.add(newx); } } } } } } //System.out.println("LA: "+opt[3][5][4][8]); if (opt[sy][sx][ey][ex] == -1) { return -1; } //System.out.println("OPT TEST: "+opt[2][2][4][5]); //test = 0; //T = 3; best = 2000000000; recurse(0); /* if (true) { return 0; } if (T > 0) { // we try here without something added // i should write code here TOrder = 0; recurse(0); } else { // we have the solution } */ return best; } }