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
mg's solution for 400: GivesYouWings, written in Java, submitted on 09.05.2010 12:56:14
import java.util.Stack; public class GivesYouWings { /** * @param args */ public class tocka { int i, j; int t; boolean[][] redbuls; } public int solve(String[] maze) { int height = maze.length; int width = maze[0].length(); char m[][] = new char[height][width]; int times[][] = new int[height][width]; boolean visited[][] = new boolean[height][width]; boolean redbuls[][] = new boolean[height][width]; for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { times[i][j] = Integer.MAX_VALUE; } } tocka start = new tocka(); tocka end = new tocka(); for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { m[i][j] = maze[i].charAt(j); if (m[i][j] == 'S') { start.i = i; start.j = j; start.t = 256; } if (m[i][j] == 'T') { end.i = i; end.j = j; } if (m[i][j] == '*') { redbuls[i][j] = true; } } } start.redbuls = new boolean[height][width]; for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { start.redbuls[i][j] = redbuls[i][j]; } } times[start.i][start.j] = 0; Stack<tocka> st = new Stack<tocka>(); st.push(start); int di[] = new int[] { 0, -1, 0, 1 }; int dj[] = new int[] { -1, 0, 1, 0 }; while (!st.empty()) { tocka cur = st.pop(); boolean rb[][] = new boolean[height][width]; for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { rb[i][j] = cur.redbuls[i][j]; } } if (cur.redbuls[cur.i][cur.j] == true) { cur.t /= 2; cur.redbuls[cur.i][cur.j] = false; } for (int dd = 0; dd < dj.length; dd++) { if ((cur.i + di[dd] < 0) || (cur.i + di[dd] >= height) || (cur.j + dj[dd] < 0) || (cur.j + dj[dd] >= width) || (m[cur.i + di[dd]][cur.j + dj[dd]] == '#')) continue; if (times[cur.i + di[dd]][cur.j + dj[dd]] > times[cur.i][cur.j] + cur.t) { times[cur.i + di[dd]][cur.j + dj[dd]] = times[cur.i][cur.j] + cur.t; visited[cur.i][cur.j] = true; tocka newtocka = new tocka(); newtocka.i = cur.i + di[dd]; newtocka.j = cur.j + dj[dd]; newtocka.t = cur.t; newtocka.redbuls = new boolean[height][width]; for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { newtocka.redbuls[i][j] = cur.redbuls[i][j]; } } st.add(newtocka); } } } if (times[end.i][end.j] == Integer.MAX_VALUE) return -1; else return times[end.i][end.j]; } public static void main(String[] args) { // TODO Auto-generated method stub System.out.println(new GivesYouWings().solve(new String[] {"S........","...####..","....*.#..",".........","........T"})); } }