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 int m_controlSum;
private int m_bonuses; // 0x000...00ggggbbb; g - good, b - bad
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;
}
public void controlSumUpdate() {
m_controlSum = (m_bombs << 8) + (m_str << 4) + m_speed;
}
/** Add bonus to bit-mask */
public void addBonus (char _b) {
switch (_b) {
case 'b': m_bonuses |= m_goodBonus[0]; break;
case 'v': m_bonuses |= m_goodBonus[1]; break;
case 'f': m_bonuses |= m_goodBonus[2]; break;
case 'r': m_bonuses |= m_badBonus[0]; m_infict = true; break;
case 's': m_bonuses |= m_badBonus[1]; m_infict = true; break;
case 'u': m_bonuses |= m_badBonus[2]; m_infict = true; break;
case 'o': m_bonuses |= m_badBonus[3]; m_infict = true; break;
}
}
/** Remove bonus from bit-mask */
public void delBonus (char _b ) {
m_infict = true;
switch (_b) {
case 'b': m_bonuses &= m_delMask[0]; break;
case 'v': m_bonuses &= m_delMask[1]; break;
case 'f': m_bonuses &= m_delMask[2]; break;
case 'r': m_bonuses &= m_delMask[3]; m_infict = false; break;
case 's': m_bonuses &= m_delMask[4]; m_infict = false; break;
case 'u': m_bonuses &= m_delMask[5]; m_infict = false; break;
case 'o': m_bonuses &= m_delMask[6]; m_infict = false; break;
}
}
public void randomAdd()
{
int newControlSum = (m_bombs << 8) + (m_str << 4) + m_speed;
newControlSum = (m_controlSum ^ newControlSum);
if (newControlSum == 0) {} //TODO: check for bonuses 'r' and 'u' should be resolved in some way...
else if ((newControlSum >>= 4) == 0) {
if(m_infict) addBonus('s');
else addBonus('v');
}
else if ((newControlSum >>= 4) == 0) addBonus('f');
else {
if(m_infict) addBonus('o');
else addBonus('b');
}
controlSumUpdate();
}
public boolean checkBonus (char _b) {
switch (_b) {
case 'b': return (m_bonuses & m_goodBonus[0]) != 0;
case 'v': return (m_bonuses & m_goodBonus[1]) != 0;
case 'f': return (m_bonuses & m_goodBonus[2]) != 0;
case 'r': return (m_bonuses & m_badBonus[0]) != 0;
case 's': return (m_bonuses & m_badBonus[1]) != 0;
case 'u': return (m_bonuses & m_badBonus[2]) != 0;
case 'o': return (m_bonuses & m_badBonus[3]) != 0;
}
/* throw hidden exception!!! */
int error = 0; int isHere = 1 / error;
return false;
}
public final int[] m_goodBonus = {0x40, 0x20, 0x10}; // 'b', 'v', 'f'
public final int[] m_badBonus = {0x8, 0x4, 0x2, 0x1}; // 'r', 's', 'u', 'o'
public final int[] m_delMask = {0x3F, 0x5F, 0x6F, 0x77, 0x7B, 0x7D, 0x7E}; // 'b', 'v', 'f', 'r', 's', 'u', 'o'
}
/*****/
class Bomb implements Cloneable, Comparable<Bomb>
{
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(Bomb _rhs) {
if (m_timer != _rhs.m_timer) return m_timer - _rhs.m_timer;
else return m_radius - _rhs.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<Bomb> m_bombs;
public int m_scale;
public int m_tick;
// Bot's state
Player m_bot;
public Point m_ourBomb;
public BotEnv(String[] _args) {
m_host = _args[0];
m_port = Utils.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) {
boolean analysis = m_P.parse(_cmd);
return m_tick == -1 ? "" : m_AB.processTactics(analysis);
}
public static void main(String[] _args) {
new BotEnv(_args).m_SM.run();
}
// debug
public void traceMap() {
System.out.println("========================");
for (int i = 0; i < m_map.length; i++) System.out.println(m_map[i]);
System.out.println("========================");
}
public final int BOMB_TIME_TICKS = 40;
public final int MAP_MAX_SIZE = 25;
}
/*** 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<Byte> m_steps;
private int m_internalCounter;
private boolean m_stayHereTactick;
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<Byte>();
}
public String processTactics(boolean _analysis) {
boolean putBomb = false;
int x = m_BE.m_bot.m_pos.x / m_BE.m_scale, y = m_BE.m_bot.m_pos.y / m_BE.m_scale;
Point newBomb = new Point(x, y);
if (_analysis || (m_steps.size() == 0 && !m_stayHereTactick)) {
m_stayHereTactick = false;
m_steps.clear();
makeDangerMap();
if (m_dangerMap[y][x] == Integer.MAX_VALUE) {
m_BE.m_bombs.add(new Bomb(newBomb, m_BE.m_bot.m_str, m_BE.m_tick + m_BE.BOMB_TIME_TICKS));
int[][] tmp = m_dangerMap;
m_dangerMap = new int[m_BE.MAP_MAX_SIZE][m_BE.MAP_MAX_SIZE];
makeDangerMap();
int dangerLvl = getBestPath();
if (dangerLvl == Integer.MAX_VALUE) putBomb = true;
else {
// Tactick 1: go to nearest unused safe cell
m_dangerMap = tmp;
goToNearestSafeCell();
}
m_BE.m_bombs.remove(m_BE.m_bombs.size() - 1);
}
// TODO: make this O(1) by LinkedList without ArrayList
else getBestPath();
}
System.out.println(m_dangerMap[y][x]);
int step;
if (m_stayHereTactick) 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'; m_BE.m_ourBomb = newBomb; }
res += ';';
return res;
}
/**
* Extract method can be applied here with getBestPath()
* But it's temporary solution so do nothing =)
*/
private void goToNearestSafeCell() {
Player me = m_BE.m_bot;
int pos, pos2, bestPos = -1;
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;
int fromX = me.m_pos.x / sz, fromY = me.m_pos.y / sz;
m_queue[tail++] = pos = (me.m_pos.x << 10) + me.m_pos.y;
m_par[pos] = -1;
m_used[pos] = ++m_internalCounter;
/*
* Find the nearest sell in unused safe sector via BFS (additional),
* and save all pathes in m_par[] array
*/
bfs: while (tail != head)
{
pos = m_queue[head++];
x = pos >> 10; y = pos & 0x3FF;
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;
wX = x2 / sz; wY = y2 / sz;
if (x2 >= 0 && x2 < mapWidth && y2 >= 0 && y2 < mapHeight
&& m_used[pos2] != m_internalCounter && m_dangerMap[wY][wX] == INF)
{
m_used[pos2] = m_internalCounter;
m_par[pos2] = pos;
m_queue[tail++] = pos2;
if (wX != fromX || wY != fromY) {
bestPos = pos2;
break bfs;
}
}
}
}
// Is the best choice to do nothing?
if (bestPos == -1) {
m_stayHereTactick = true;
return;
}
byte step = -1;
int pathLength = 0;
while (m_par[bestPos] != -1) {
pos2 = bestPos; pos = m_par[bestPos];
x = pos >> 10; y = pos & 0x3FF;
x2 = pos2 >> 10; y2 = pos2 & 0x3FF;
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];
pathLength++;
}
for (int i = 0; i < 5; i++) m_steps.add((byte)4);
}
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] == '.') ? Integer.MAX_VALUE : -1;
/*
* 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; cy = bombs[k].m_pos.y;
r = bombs[k].m_radius; t = bombs[k].m_timer - m_BE.m_tick;
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 < mapHeight
&& 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 pathLength = 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];
pathLength++;
}
// dbg
// System.out.println("length: " + pathLength);
// for (int i = 0; i < m_steps.size(); i++)
// System.out.print(m_steps.get(i));
// System.out.println();
// Is the best choice to do nothing?
if ((dangerLvl != INF || pathLength > m_BE.BOMB_TIME_TICKS)
&& m_dangerMap[me.m_pos.y / sz][me.m_pos.x / sz] == INF) {
m_stayHereTactick = true;
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 boolean parse (String _cmd) {
switch(_cmd.charAt(0)) {
case 'P': playerIdComand(_cmd); break;
case 'S': startComand(_cmd); break;
case 'R': roundEnd(_cmd); break;
case 'G': gameEnd(_cmd); break;
case 'T': return timerTick(_cmd);
}
return false;
}
private void playerIdComand (String _cmd) {
// At this stage map is ignored
m_BE.m_bot.m_pid = Utils.parseInt(_cmd, 3);
}
private void startComand (String _cmd) {
m_BE.m_bombs = new ArrayList<Bomb>(20);
int idx = _cmd.indexOf('&') + 1;
m_BE.m_scale = Utils.parseInt(_cmd, idx);
String[] map = _cmd.substring(_cmd.indexOf(' ')).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);
}
private boolean timerTick (String _cmd) {
boolean needAnalysis = false;
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 && parts[p].length() != 0) needAnalysis = parseTickChangesPart(parts[p]);
//else if (p == 3 && parts[p].length() != 0) parseTickDangerPart(parts[p]);
return needAnalysis;
}
private void parseTickTimePart (String _cmd) {
m_BE.m_tick = Utils.parseInt(_cmd.substring(1));
}
private void parseTickSapkaPart (String _cmd) {
int pid;
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 = Utils.parseInt(cur[0], 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.x = -1;
else {
link.m_pos = new Point(Utils.parseInt(cur[1]), Utils.parseInt(cur[2]));
link.m_bombs = Utils.parseInt(cur[3]);
link.m_str = Utils.parseInt(cur[4]);
link.m_speed = Utils.parseInt(cur[5]);
link.m_infict = cur.length == 7;
//m_BE.traceMap();
}
}
}
private boolean parseTickChangesPart (String _cmd) {
boolean needTactickAnalysis = false;
String[] changes = _cmd.split(","), current;
boolean isAdded = false; // Add or remove
char type, mapMark;
int x, y;
for (int i = 0; i < changes.length; i++) {
current = changes[i].trim().split(" "); // Parse <change-info>
isAdded = current[0].charAt(0) == '+'; // Parse common parts
type = current[0].charAt(1);
x = Utils.parseInt(current[1]);
y = Utils.parseInt(current[2]);
mapMark = isAdded ? type : '.';
switch (type)
{
case '*': // Bomb
{
Point pos = new Point(x, y);
if (pos.equals(m_BE.m_ourBomb)) {
if (!isAdded) m_BE.m_ourBomb = null;
}
else needTactickAnalysis = true;
if (pos.equals(m_BE.m_ourBomb) == false) needTactickAnalysis = true;
if (isAdded) m_BE.m_bombs.add(new Bomb(pos, Utils.parseInt(current[3]), Utils.parseInt(current[4])));
else for (int k = 0; k < m_BE.m_bombs.size(); k++)
if (m_BE.m_bombs.get(k).m_pos.equals(pos)) {
m_BE.m_bombs.remove(k);
break;
}
} break;
case '#': // Explode
{
mapMark = '.';
} break;
case 'w': // Destructable wall
{
} break;
case 'X': // Indestructable wall
{
} break;
default: // Bonuses
{
} break;
}
m_BE.m_map[y][x] = mapMark;
//m_BE.traceMap();
}
return needTactickAnalysis;
}
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...
}
}
/*****/
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();
//System.out.println("Result: " + res);
}
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;";
}
/*****/
class Utils
{
static public int parseInt(String _str, int _startIndex) {
int number = 0, len = _str.length();
char ch;
while (_startIndex < len) {
ch = _str.charAt(_startIndex);
if (ch >= '0' && ch <= '9') { number = number * 10 + ch - '0'; _startIndex++; }
else break;
}
return number;
}
static public int parseInt(String _str) {
return parseInt(_str, 0);
}
}