import java.io.*; import java.net.*; import java.util.*; import java.awt.Point; /*****/ class Player { public int m_pid; public Point m_pos; public int m_bombs; public int m_str; public int m_speed; public boolean m_infict; public Player() {} public Player(int _pid, Point _pos, int _bombs, int _bombsStrength, int _speed, boolean _isInfected) { m_pid = _pid; m_pos = _pos; m_bombs = _bombs; m_str = _bombsStrength; m_speed = _speed; m_infict = _isInfected; } } /*****/ class Bomb implements Cloneable, Comparable { public Point m_pos; public int m_radius; public int m_timer; public Bomb (Point _pos, int _damage, int _time) { m_pos = _pos; m_radius = _damage; m_timer = _time; } public Bomb clone() { Bomb copy = new Bomb(m_pos, m_radius, m_timer); return copy; } public int compareTo(Object _b) { Bomb bomb = (Bomb)_b; if (m_timer != bomb.m_timer) return m_timer - bomb.m_timer; else return m_radius - bomb.m_radius; } } /*****/ public class BotEnv { private SocketMaster m_SM; private AlgoBrain m_AB; private Parser m_P; // connection parameters private String m_host; private int m_port; // World's state public char[][] m_map; public Player[] m_enemies; public ArrayList m_bombs = new ArrayList(); public int m_scale; public int m_tick; // Bot's state Player m_bot; public BotEnv(String[] _args) { m_host = _args[0]; m_port = Integer.parseInt(_args[1]); m_SM = new SocketMaster(this, m_host, m_port); m_P = new Parser(this); m_AB = new AlgoBrain(this); m_bot = new Player(); m_tick = -1; } public String proccessComand (String _cmd) { m_P.parse(_cmd); return m_tick == -1 ? "" : m_AB.processTactics(); } public static void main(String[] _args) { new BotEnv(_args).m_SM.run(); } public final int BOMB_TIME_TICKS = 40; public final int MAP_MAX_SIZE = 25; } /*****/ class SocketMaster { private BotEnv m_BE; private Socket m_sock; private Scanner m_in; private PrintWriter m_out; public SocketMaster (BotEnv _bptr, String _host, int _port) { m_BE = _bptr; try { m_sock = new Socket(_host, _port); m_in = new Scanner(m_sock.getInputStream()); m_out = new PrintWriter(m_sock.getOutputStream()); } catch (Exception _e) { _e.printStackTrace(); } } public void run() { m_out.println(INIT_STRING); m_out.flush(); int idx; boolean started = false; String startLex = "PID"; String res; // Here we going to get all fucking shit, from task details to input stream... String get, cmd = "", put; while (m_in.hasNext()) { get = m_in.next(); if (!started) { idx = get.indexOf(startLex); if (idx != -1) { cmd = get.substring(idx); started = true; } } else { idx = get.indexOf(';'); if (idx != -1) { cmd += get.substring(0, idx); System.out.println(cmd); // IMPORTANT! Here we will instantly give out solution response!!! res = m_BE.proccessComand(cmd); if (res.length() != 0) { m_out.print(res); m_out.flush(); } cmd = get.substring(idx+1) + " "; } else cmd += get + " "; } } } private final String INIT_STRING = "launch heratorz CFGSrUPQPKgtmDcKuOhgCSy#CFGwjQJiWQQUViJiymrQoGY#CFGUfimkSUQhcMgGMqlWQYs#CFGWYiZmCiYpYaYWZuBspkg#CFGAEeaubIIRkDOlIxGmyPM#CFGYLEQYicsFWmjwKmXaOmC#CFGufAMuyIOhKxKaSOxoxUN#CFGowmRWjWSWxcZiqlGeYkF#CFGUpogIViMtiOkulA@IYoZ#CFGQOwAkDwyVAZCoKTqFuyJ#CFGMSYfClQgVEaUuinytily#CFGyNQRgQmanQxKmUAXEepm;"; } /*** Powerful bot's brain mega-buster!!! **/ class AlgoBrain { private BotEnv m_BE; private int[][] m_dangerMap; private int[] m_par; private int[] m_queue; private int[] m_used; private ArrayList m_steps; private int m_internalCounter; public AlgoBrain (BotEnv _bptr) { m_BE = _bptr; m_dangerMap = new int[m_BE.MAP_MAX_SIZE][m_BE.MAP_MAX_SIZE]; m_par = new int[CACHE_SIZE]; m_queue = new int[CACHE_SIZE]; m_used = new int[CACHE_SIZE]; m_steps = new ArrayList(); } public String processTactics() { boolean putBomb = false; m_steps.clear(); makeDangerMap(); int dangerLvl = getBestPath(); // Try to put bomb here... if (dangerLvl == Integer.MAX_VALUE && m_BE.m_bot.m_bombs != 0) { ArrayList tmp = (ArrayList)m_steps.clone(); m_BE.m_bombs.add(new Bomb(m_BE.m_bot.m_pos, m_BE.m_bot.m_str, m_BE.m_tick + m_BE.BOMB_TIME_TICKS)); makeDangerMap(); int dangerLvl2 = getBestPath(); if (dangerLvl2 != Integer.MAX_VALUE) m_steps = tmp; else putBomb = true; // TODO: make this O(1) by LinkedList without ArrayList m_BE.m_bombs.remove(m_BE.m_bombs.size() - 1); } // TODO: make this O(1) by LinkedList without ArrayList int step; if (m_steps.size() == 0) step = 4; else { step = m_steps.get(m_steps.size() - 1); m_steps.remove(m_steps.size() - 1); } String res = "" + MOVES[step]; if (putBomb) res += 'b'; res += ';'; return res; } private void makeDangerMap() { final int mapWidth = m_BE.m_map[0].length; final int mapHeight = m_BE.m_map.length; final int sz = m_BE.m_scale; int head, tail; char[][] map = m_BE.m_map; Bomb[] bombs = new Bomb[m_BE.m_bombs.size()]; boolean[] used = new boolean[bombs.length]; // Sort bombs in appriate way for (int i = 0; i < bombs.length; i++) bombs[i] = m_BE.m_bombs.get(i).clone(); Arrays.sort(bombs); // Fill all cells as safe for (int i = 0; i < mapHeight; i++) for (int j = 0; j < mapWidth; j++) m_dangerMap[i][j] = (map[i][j] == 'X' || map[i][j] == 'w') ? -1 : Integer.MAX_VALUE; /* * Paint the dangerous map by performing BFS (1st) on bombs array * to pay attention to detonation cess * TODO: update knowing burst speed! */ int k, cx, cy, r, t; for (int i = 0; i < bombs.length; i++) { if (used[i]) continue; head = tail = 0; m_queue[tail++] = i; while (tail != head) { k = m_queue[head++]; cx = bombs[k].m_pos.x / sz; cy = bombs[k].m_pos.y / sz; r = bombs[k].m_radius; t = bombs[k].m_timer; m_dangerMap[cy][cx] = t; left: for (int dx = cx-1; dx >= cx-r; dx--) if (dx < 0 || m_dangerMap[cy][dx] == -1) break; else if (map[cy][dx] != 'B') m_dangerMap[cy][dx] = Math.min(m_dangerMap[cy][dx], t); else if (dx != cx) for (int j = 0; j < bombs.length; j++) if (bombs[j].m_pos.x == dx && bombs[j].m_pos.y == cy) { bombs[j].m_timer = t; m_queue[tail++] = j; break left; } right: for (int dx = cx+1; dx <= cx+r; dx++) // Go right if (dx == mapWidth || m_dangerMap[cy][dx] == -1) break; else if (map[cy][dx] != 'B') m_dangerMap[cy][dx] = Math.min(m_dangerMap[cy][dx], t); else if (dx != cx) for (int j = 0; j < bombs.length; j++) { bombs[j].m_timer = t; m_queue[tail++] = j; break right; } up: for (int dy = cy-1; dy >= cy-r; dy--) // Go up if (dy < 0 || m_dangerMap[dy][cx] == -1) break; else if (map[dy][cx] != 'B') m_dangerMap[dy][cx] = Math.min(m_dangerMap[dy][cx], t); else if (dy != cy) for (int j = 0; j < bombs.length; j++) if (bombs[j].m_pos.x == cx && bombs[j].m_pos.y == dy) { bombs[j].m_timer = t; m_queue[tail++] = j; break up; } down: for (int dy = cy+1; dy <= cx+r; dy++) // Go down if (dy == mapHeight || m_dangerMap[dy][cx] == -1) break; else if (map[dy][cx] != 'B') m_dangerMap[dy][cx] = Math.min(m_dangerMap[dy][cx], t); else if (dy != cy) for (int j = 0; j < bombs.length; j++) if (bombs[j].m_pos.x == cx && bombs[j].m_pos.y == dy) { bombs[j].m_timer = t; m_queue[tail++] = j; break down; } } } System.out.println("=============================="); for (int i = 0; i < mapHeight; i++) { for (int j = 0; j < mapWidth; j++) if (m_dangerMap[i][j] == Integer.MAX_VALUE) System.out.printf("%s\t", "I"); else System.out.printf("%d\t", m_dangerMap[i][j]); System.out.println(""); } System.out.println("=============================="); } /* * Paint the dangerous map by performing BFS (1st) on bombs array * to pay attention to detonation cess * TODO: update knowing burst speed! */ private int getBestPath() { Player me = m_BE.m_bot; int dangerLvl = -1, bestPos; int pos, pos2; int x, y, x2, y2, wX, wY, tail, head; tail = head = 0; final int sz = m_BE.m_scale; final int mapWidth = m_BE.m_map[0].length * sz; final int mapHeight = m_BE.m_map.length * sz; final int INF = Integer.MAX_VALUE; m_queue[tail++] = bestPos = pos = // ENCODE (me.m_pos.x << 10) + me.m_pos.y; m_par[pos] = -1; m_used[pos] = ++m_internalCounter; /* * Find the nearest safe or least dangerous cell via BFS (2nd), * and save all pathes in m_par[] array */ bfs: while (tail != head) { pos = m_queue[head++]; x = pos >> 10; y = pos & 0x3FF; // DECODE for (int i = 0; i < 4; i++) { x2 = x + DX[i] * me.m_speed; y2 = y + DY[i] * me.m_speed; pos2 = (x2 << 10) + y2; // ENCODE wX = x2 / sz; wY = y2 / sz; if (x2 >= 0 && x2 < mapWidth && y2 >= 0 && y2 < mapWidth && m_used[pos2] != m_internalCounter && m_dangerMap[wY][wX] != -1) { m_used[pos2] = m_internalCounter; m_par[pos2] = pos; m_queue[tail++] = pos2; if (m_dangerMap[wY][wX] > dangerLvl) { dangerLvl = m_dangerMap[wY][wX]; bestPos = pos2; if (dangerLvl == INF) break bfs; } } } } byte step = -1; int pathLenght = 0; while (m_par[bestPos] != -1) { pos2 = bestPos; pos = m_par[bestPos]; x = pos >> 10; y = pos & 0x3FF; // DECODE x2 = pos2 >> 10; y2 = pos2 & 0x3FF; // DECODE if (x2 == x - me.m_speed && y2 == y) step = 0; else if (x2 == x && y2 == y - me.m_speed) step = 1; else if (x2 == x + me.m_speed && y2 == y) step = 2; else if (x2 == x && y2 == y + me.m_speed) step = 3; /* throw hidden exception!!! */ else {int error = 0; int isHere = 1 / error; } m_steps.add(step); bestPos = m_par[bestPos]; pathLenght++; } // Is the best choice to do nothing? if ((dangerLvl != INF || pathLenght > m_BE.BOMB_TIME_TICKS) && m_dangerMap[me.m_pos.y / sz][me.m_pos.x / sz] == INF) { m_steps.clear(); return INF; } return dangerLvl; } private final char[] MOVES = {'l', 'u', 'r', 'd', 's'}; private final byte[] DX = {-1, 0, 1, 0}; private final byte[] DY = {0, 1, 0, -1}; private final int CACHE_SIZE = 650000; } /*****/ class Parser { private BotEnv m_BE; public Parser(BotEnv _bptr) { m_BE = _bptr; } public void parse (String _cmd) { switch(_cmd.charAt(0)) { case 'P': playerIdComand(_cmd); break; case 'S': startComand(_cmd); break; case 'T': timerTick(_cmd); break; case 'R': roundEnd(_cmd); break; case 'G': gameEnd(_cmd); break; } } private void playerIdComand (String _cmd) { // At this stage map is ignored int pid = 0, idx = 3; while (_cmd.charAt(idx) >= '0' && _cmd.charAt(idx) <= '9') pid = pid * 10 + _cmd.charAt(idx++) - '0'; m_BE.m_bot.m_pid = pid; } private void startComand (String _cmd) { int idx = _cmd.indexOf('&') + 1; int scale = 0; while (_cmd.charAt(idx) >= '0' && _cmd.charAt(idx) <= '9') scale = scale * 10 + _cmd.charAt(idx++) - '0'; String[] map = _cmd.substring(idx).trim().split(" "); int h = map.length, w = map[0].length(); m_BE.m_map = new char[h][w]; for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) m_BE.m_map[i][j] = map[i].charAt(j); m_BE.m_scale = scale; } private void timerTick (String _cmd) { String[] parts = _cmd.trim().split("&"); for (int p = 0; p < parts.length; p++) if (p == 0) parseTickTimePart(parts[p]); else if (p == 1) parseTickSapkaPart(parts[p]); else if (p == 2) parseTickChangesPart(parts[p]); } private void parseTickTimePart (String _cmd) { m_BE.m_tick = Integer.parseInt(_cmd.substring(1)); } private void parseTickSapkaPart (String _cmd) { int pid;//, x = -1, y = -1, bombs = -1, strength = -1, speed = -1; boolean inficted = false; Player link; String[] pl = _cmd.trim().split(","); String[] cur; if (m_BE.m_enemies == null) { m_BE.m_enemies = new Player[pl.length-1]; for (int i = 0; i < pl.length-1; i++) m_BE.m_enemies[i] = new Player(); } int k = 0; for (int i = 0; i < pl.length; i++) { cur = pl[i].trim().split(" "); pid = Integer.parseInt(cur[0].substring(1)); link = (pid == m_BE.m_bot.m_pid) ? m_BE.m_bot : m_BE.m_enemies[k++]; if (cur.length == 2) link.m_pos = null; else { link.m_pos = new Point(Integer.parseInt(cur[1]), Integer.parseInt(cur[2])); link.m_bombs = Integer.parseInt(cur[3]); link.m_str = Integer.parseInt(cur[4]); link.m_speed = Integer.parseInt(cur[5]); link.m_infict = cur.length == 7; } } } private void parseTickChangesPart (String _cmd) { if (_cmd.length() == 0) return; String[] chp = _cmd.split(","); String[] cur; boolean add = false; char type; for (int i = 0; i < chp.length; i++) { cur = chp[i].trim().split(" "); for (int j = 0; j < cur.length; j++) { add = cur[0].charAt(0) == '+'; type = cur[0].charAt(1); switch (type) { // Bomb case '*': { } break; // Explode case '#': { } break; // Destructable wall case 'w': { } break; // Indestructable wall case 'X': { } break; // Bonuses default: { } break; } } } } private void roundEnd(String _cmd) { m_BE.m_enemies = null; m_BE.m_bombs = null; m_BE.m_tick = -1; } private void gameEnd(String _cmd) { // Nothing to do... } }