#include <unistd.h>
#include <cstdlib>
#include <cstring>
#include <math.h>
#include <string>
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <algorithm>
#include <stdint.h>

#define MAX_MATRIX_WIDTH (1024)

#define MOVE_NONE (-1)

#define MOVE_UP (0)
#define MOVE_RIGHT (1)
#define MOVE_DOWN (2)
#define MOVE_LEFT (3)

#define ENEMY_V (1)
#define ENEMY_H (2)
#define ENEMY_L (3)
#define ENEMY_R (4)
#define ENEMY_J1 (5)
#define ENEMY_J2 (6)

typedef char Direction;

class GameField;
class Pos {
public:
    int x_;
    int y_;
    Pos() :
        x_(-1), y_(-1) {
    }
    Pos(int x, int y) :
        x_(x), y_(y) {
    }
    void set(int x, int y) {
        x_ = x;
        y_ = y;
    }
    bool equal(int x, int y) const {
        if (x_ != x || y_ != y) return false;
        return true;
    }
    bool operator==(const Pos& pos) {
        return equal(pos.x_, pos.y_);
    }
    bool isUndef() const {
        if (x_ == -1 || y_ == -1) return true;
        return false;
    }
};

class Foods {
public:
    Pos matrix_;
    int num_;
    bool *data_;
    struct StepLog {
        Pos pos_;
        bool feed_;
        StepLog(Pos pos, bool feed) :
            pos_(pos), feed_(feed) {
        }
    };
    std::vector<StepLog> log_;

    Foods() :
        num_(0), data_(NULL) {
    }
    Foods(const Foods& obj) :
        matrix_(obj.matrix_), num_(obj.num_) {
        data_ = new bool[matrix_.x_ * matrix_.y_];
        std::memcpy(data_, obj.data_, matrix_.x_ * matrix_.y_ * sizeof(bool));
    }

    ~Foods() {
        if (data_ != NULL) {
            delete[] data_;
            data_ = NULL;
        }
    }

    void init(const Pos& matrix) {
        num_ = 0;
        matrix_ = matrix;
        if (data_ != NULL) delete[] data_;
        data_ = new bool[matrix_.x_ * matrix_.y_];
        std::memset(data_, 0, matrix_.x_ * matrix_.y_ * sizeof(bool));
    }

    void set(int x, int y, bool flag) {
        data_[y * matrix_.x_ + x] = flag;
    }

    void add(int x, int y) {
        set(x, y, true);
        num_++;
    }

    void rollback(int step) {
        while ((int) log_.size() > step) {
            StepLog step_log = log_.back();
            if (step_log.feed_) {
                add(step_log.pos_.x_, step_log.pos_.y_);
            }
            log_.pop_back();
        }
    }

    bool exists(int step, int x, int y) {
        rollback(step);
        return data_[y * matrix_.x_ + x];
    }

    bool exists(int x, int y) const {
        return data_[y * matrix_.x_ + x];
    }

    bool exists(int step, const Pos& pos) {
        return exists(step, pos.x_, pos.y_);
    }

    bool eat(int step, const Pos& pos) {
        bool result = exists(step, pos);
        if (result) {
            set(pos.x_, pos.y_, false);
            num_--;
        }
        log_.push_back(StepLog(pos, result));
        return result;
    }
};

class Movable {
public:
    Pos pos_;
    Pos prev_;

    Movable() {
    }

    Movable(int x, int y) :
        pos_(x, y) {
    }

    Pos getDirectedPos(Direction direction);
    bool move(const GameField* game_field, Direction direction);

    Direction getForward(const GameField* game_field);
    Direction getCurrentDirection();
};

class Enemy: public Movable {
public:
    int type_;

    Enemy(int type, int x, int y) :
        Movable(x, y), type_(type) {
    }

    char getCode() const {
        switch (type_) {
            case ENEMY_V:
                return 'V';
            case ENEMY_H:
                return 'H';
            case ENEMY_L:
                return 'L';
            case ENEMY_R:
                return 'R';
            case ENEMY_J1:
                return 'J';
            case ENEMY_J2:
                return 'j';
        }
        return 'X';
    }
    bool next(const GameField* game_field, Pos player_pos);
    bool nextGeneric(const GameField* game_field);
    bool nextV(const GameField* game_field, Pos player_pos);
    bool nextH(const GameField* game_field, Pos player_pos);
    bool nextL(const GameField* game_field);
    bool nextR(const GameField* game_field);
    bool nextJ(const GameField* game_field);
    Pos getRelativePlayerPos(const GameField* game_field, Pos player_pos);
};

typedef std::vector<Enemy> EnemyList;

class GameField {
public:
    int max_step_;
    Pos matrix_;

    Foods foods_;
    Movable player_;
    EnemyList enemies_;

private:
    bool *walls_;

public:
    GameField() :
        max_step_(0), matrix_(), walls_(NULL) {
    }

    ~GameField() {
        if (walls_ != NULL) {
            delete[] walls_;
            walls_ = NULL;
        }
    }

    void init(const char* filename) {
        char buf[MAX_MATRIX_WIDTH + 1];
        std::ifstream ifs(filename, std::ios::in);
        std::cout << "filename : " << filename << "\n";

        if (ifs.eof()) exit(EXIT_FAILURE);
        ifs.getline(buf, sizeof(buf));
        max_step_ = std::atoi(buf);
        std::cout << "max_step : " << max_step_ << "\n";

        if (ifs.eof()) exit(EXIT_FAILURE);
        ifs.getline(buf, sizeof(buf));
        matrix_.x_ = std::atoi(buf);
        const char* p = std::strchr(buf, ' ');
        if (p == NULL) exit(EXIT_FAILURE);
        matrix_.y_ = std::atoi(p);

        std::cout << "matrix : " << matrix_.x_ << " x " << matrix_.y_ << "\n";
        if (matrix_.x_ == 0 || matrix_.y_ == 0) exit(EXIT_FAILURE);

        walls_ = new bool[matrix_.x_ * matrix_.y_];
        std::memset(walls_, 0, matrix_.x_ * matrix_.y_ * sizeof(bool));

        foods_.init(matrix_);

        int y = 0;
        while (!ifs.eof()) {
            ifs.getline(buf, sizeof(buf));
            if ((int) std::strlen(buf) != matrix_.x_) continue;
            for (int x = 0; x < matrix_.x_; x++) {
                const char c = buf[x];
                switch (c) {
                    case '#':
                        walls_[y * matrix_.x_ + x] = true;
                        break;
                    case '.':
                        foods_.add(x, y);
                        break;
                    case '@':
                        player_.pos_.set(x, y);
                        break;
                    case 'V':
                        enemies_.push_back(Enemy(ENEMY_V, x, y));
                        break;
                    case 'H':
                        enemies_.push_back(Enemy(ENEMY_H, x, y));
                        break;
                    case 'L':
                        enemies_.push_back(Enemy(ENEMY_L, x, y));
                        break;
                    case 'R':
                        enemies_.push_back(Enemy(ENEMY_R, x, y));
                        break;
                    case 'J':
                        enemies_.push_back(Enemy(ENEMY_J1, x, y));
                        break;
                }
            }
            y++;
        }
        ifs.close();
        std::cout << "Initialized.\n";
    }

    bool isWall(int x, int y) const {
        return walls_[y * matrix_.x_ + x];
    }
    bool isWall(const Pos& pos) const {
        return isWall(pos.x_, pos.y_);
    }
};
bool Movable::move(const GameField* game_field, Direction direction) {
    Pos next_pos = getDirectedPos(direction);
    if (game_field->isWall(next_pos)) return false;
    prev_ = pos_;
    pos_ = next_pos;
    return true;
}

Pos Movable::getDirectedPos(Direction direction) {
    Pos next_pos = pos_;
    switch (direction) {
        case MOVE_UP:
            next_pos.y_--;
            break;
        case MOVE_DOWN:
            next_pos.y_++;
            break;
        case MOVE_LEFT:
            next_pos.x_--;
            break;
        case MOVE_RIGHT:
            next_pos.x_++;
            break;
    }
    return next_pos;
}

Direction Movable::getForward(const GameField* game_field) {
    int num = 0;
    Direction forward = MOVE_NONE;
    Direction backword = MOVE_NONE;
    if (!game_field->isWall(pos_.x_, pos_.y_ - 1)) {
        if (prev_.equal(pos_.x_, pos_.y_ - 1)) backword = MOVE_UP;
        else {
            forward = MOVE_UP;
            num++;
        }
    }
    if (!game_field->isWall(pos_.x_, pos_.y_ + 1)) {
        if (prev_.equal(pos_.x_, pos_.y_ + 1)) backword = MOVE_DOWN;
        else {
            forward = MOVE_DOWN;
            num++;
        }
    }
    if (!game_field->isWall(pos_.x_ - 1, pos_.y_)) {
        if (prev_.equal(pos_.x_ - 1, pos_.y_)) backword = MOVE_LEFT;
        else {
            forward = MOVE_LEFT;
            num++;
        }
    }
    if (!game_field->isWall(pos_.x_ + 1, pos_.y_)) {
        if (prev_.equal(pos_.x_ + 1, pos_.y_)) backword = MOVE_RIGHT;
        else {
            forward = MOVE_RIGHT;
            num++;
        }
    }
    if (num == 1) return forward;
    if (num == 0) return backword;
    return MOVE_NONE;
}

Direction Movable::getCurrentDirection() {
    if (pos_.y_ < prev_.y_) return MOVE_UP;
    if (pos_.y_ > prev_.y_) return MOVE_DOWN;
    if (pos_.x_ < prev_.x_) return MOVE_LEFT;
    if (pos_.x_ > prev_.x_) return MOVE_RIGHT;
    return MOVE_NONE;
}

bool Enemy::nextGeneric(const GameField* game_field) {
    if (prev_.isUndef()) {
        move(game_field, MOVE_DOWN) || move(game_field, MOVE_LEFT) || move(game_field, MOVE_UP) || move(game_field, MOVE_RIGHT);
        return true;
    }

    Direction direction = getForward(game_field);
    if (direction == MOVE_NONE) return false;
    move(game_field, direction);
    return true;
}

Pos Enemy::getRelativePlayerPos(const GameField* game_field, Pos player_pos) {
    Pos result(player_pos);
    result.x_ -= pos_.x_;
    result.y_ -= pos_.y_;
    return result;
}

bool Enemy::nextV(const GameField* game_field, Pos player_pos) {
    if (nextGeneric(game_field)) return true;

    Pos relative = getRelativePlayerPos(game_field, player_pos);
    if (relative.y_ > 0 && move(game_field, MOVE_DOWN)) return true;
    else if (relative.y_ < 0 && move(game_field, MOVE_UP)) return true;
    else if (relative.x_ > 0 && move(game_field, MOVE_RIGHT)) return true;
    else if (relative.x_ < 0 && move(game_field, MOVE_LEFT)) return true;
    move(game_field, MOVE_DOWN) || move(game_field, MOVE_LEFT) || move(game_field, MOVE_UP) || move(game_field, MOVE_RIGHT);
    return true;
}

bool Enemy::nextH(const GameField* game_field, Pos player_pos) {
    if (nextGeneric(game_field)) return true;

    Pos relative = getRelativePlayerPos(game_field, player_pos);
    if (relative.x_ > 0 && move(game_field, MOVE_RIGHT)) return true;
    else if (relative.x_ < 0 && move(game_field, MOVE_LEFT)) return true;
    else if (relative.y_ > 0 && move(game_field, MOVE_DOWN)) return true;
    else if (relative.y_ < 0 && move(game_field, MOVE_UP)) return true;
    move(game_field, MOVE_DOWN) || move(game_field, MOVE_LEFT) || move(game_field, MOVE_UP) || move(game_field, MOVE_RIGHT);
    return true;
}

bool Enemy::nextL(const GameField* game_field) {
    if (nextGeneric(game_field)) return true;
    Direction current_dir = getCurrentDirection();
    if (move(game_field, (current_dir + 3) % 4)) return true; // 左
    if (move(game_field, current_dir)) return true; // 前
    move(game_field, (current_dir + 1) % 4); // 右
    return true;
}

bool Enemy::nextR(const GameField* game_field) {
    if (nextGeneric(game_field)) return true;
    Direction current_dir = getCurrentDirection();
    if (move(game_field, (current_dir + 1) % 4)) return true; // 右
    if (move(game_field, current_dir)) return true; // 前
    move(game_field, (current_dir + 3) % 4); // 左
    return true;
}

bool Enemy::nextJ(const GameField* game_field) {
    if (nextGeneric(game_field)) return true;
    Direction current_dir = getCurrentDirection();

    if (type_ == ENEMY_J1) {
        type_ = ENEMY_J2;
        if (move(game_field, (current_dir + 3) % 4)) return true; // 左
        if (move(game_field, current_dir)) return true; // 前
        move(game_field, (current_dir + 1) % 4); // 右
    }
    else {
        type_ = ENEMY_J1;
        if (move(game_field, (current_dir + 1) % 4)) return true; // 右
        if (move(game_field, current_dir)) return true; // 前
        move(game_field, (current_dir + 3) % 4); // 左
    }
    return true;
}

bool Enemy::next(const GameField* game_field, Pos player_pos) {
    switch (type_) {
        case ENEMY_V:
            return nextV(game_field, player_pos);
        case ENEMY_H:
            return nextH(game_field, player_pos);
        case ENEMY_L:
            return nextL(game_field);
        case ENEMY_R:
            return nextR(game_field);
        case ENEMY_J1:
        case ENEMY_J2:
            return nextJ(game_field);
    }
    return false;
}

static void printMap(const GameField* game_field, const EnemyList& enemies, const Foods& foods, const Pos& player_pos) {
    for (int y = 0; y < game_field->matrix_.y_; y++) {
        for (int x = 0; x < game_field->matrix_.x_; x++) {
            if (player_pos.equal(x, y)) {
                std::cout << '@';
            }
            else if (game_field->isWall(x, y)) {
                std::cout << '#';
            }
            else {
                EnemyList::const_iterator it;
                for (it = enemies.begin(); it != enemies.end(); it++) {
                    if (it->pos_.equal(x, y)) {
                        std::cout << it->getCode();
                        break;
                    }
                }
                if (it == enemies.end()) {
                    if (foods.exists(x, y)) {
                        std::cout << '.';
                    }
                    else {
                        std::cout << ' ';
                    }
                }
            }
        }
        std::cout << '\n';
    }
}

class ResultPool {
public:
    int hunger_rate_;
    int best_step_;
    int best_foods_;

    std::list<Direction> step_log_;
    ResultPool(GameField *game_field) :
        best_step_(game_field->max_step_), best_foods_(game_field->foods_.num_) {
    }
};

class Node {
public:
    GameField *game_field_;
    ResultPool* result_pool_;
    Node* parent_;

    int step_;
    int hunger_;
    std::vector<Direction> partial_step_log_;
    EnemyList enemies_;
    Foods* foods_;
    Movable player_;
public:
    Node(GameField *game_field, ResultPool* result_pool, Foods* foods);
    ~Node();
    Node(Node* parent);
    bool walk();
    bool walkToNextNode(Direction direction);
    bool isJunkNode();
    int getCurrentMaxHunger();
    void createResult();
    void print();
};

Node::Node(GameField *game_field, ResultPool* result_pool, Foods* foods) :
    game_field_(game_field), result_pool_(result_pool), parent_(NULL), step_(0), hunger_(0), foods_(foods), player_(game_field->player_) {

    enemies_.assign(game_field_->enemies_.begin(), game_field_->enemies_.end());
}

Node::Node(Node* parent) :
    game_field_(parent->game_field_), result_pool_(parent->result_pool_), parent_(parent), step_(parent->step_), hunger_(parent->hunger_), foods_(parent->foods_), player_(parent->player_) {
    enemies_.assign(parent->enemies_.begin(), parent->enemies_.end());
}

Node::~Node() {
}

bool Node::walk() {
    Direction current_dir = player_.getCurrentDirection();
    Direction dirs[] = { current_dir, (current_dir + 1) % 4, (current_dir + 3) % 4, (current_dir + 2) % 4 };

    std::vector<Direction> available_dirs;

    for (int i = 0; i < 3; i++) {
        if (foods_->exists(step_, player_.getDirectedPos(dirs[i]))) {
            available_dirs.push_back(dirs[i]);
            dirs[i] = MOVE_NONE;
        }
    }

    if (hunger_ < getCurrentMaxHunger()) {
        for (int i = 0; i < 4; i++) {
            if (dirs[i] == MOVE_NONE) continue;
            if (!game_field_->isWall(player_.getDirectedPos(dirs[i]))) {
                available_dirs.push_back(dirs[i]);
            }
        }
    }

    for (std::vector<Direction>::iterator it = available_dirs.begin(); it != available_dirs.end(); it++) {
        Node* next_node = new Node(this);
        next_node->walkToNextNode(*it);
        foods_->rollback(step_);
        delete next_node;
    }
    return false;
}

bool Node::walkToNextNode(Direction direction) {
    bool is_hunger_node = true;
    while (true) {
        if (direction == MOVE_NONE) {
            direction = player_.getForward(game_field_);
            if (direction == MOVE_NONE) {
                // 交差点にいる
                if (is_hunger_node) {
                    hunger_++;
                }
                else {
                    hunger_ = 0;
                }
                if (isJunkNode()) return true;
                return walk();
            }
        }
        // 敵を動かす
        for (EnemyList::iterator it = enemies_.begin(); it != enemies_.end(); it++) {
            it->next(game_field_, player_.pos_);
        }

        // 自機を動かす
        player_.move(game_field_, direction);
        partial_step_log_.push_back(direction);
        direction = MOVE_NONE;

        // 死亡判定
        for (EnemyList::const_iterator it = enemies_.begin(); it != enemies_.end(); it++) {
            if (player_.pos_ == it->pos_ || (player_.prev_ == it->pos_ && player_.pos_ == it->prev_)) {
                // 死亡
                return false;
            }
        }

        // エサを食べて勝利判定
        if (foods_->eat(step_, player_.pos_)) {
            is_hunger_node = false;
            if (foods_->num_ == 0) {
                // 勝利
                createResult();
                return false;
            }
        }

        step_++;
        // タイムアップ
        if (result_pool_->best_step_ <= step_) {
            createResult();
            return false;
        }
    }
}

bool Node::isJunkNode() {
    if (hunger_ > getCurrentMaxHunger()) return true;
    if (step_ > game_field_->foods_.num_ * 3) return true;
    return false;
}

int Node::getCurrentMaxHunger() {
    if (result_pool_->hunger_rate_ == 0) return game_field_->max_step_;
    int step = (step_ - result_pool_->hunger_rate_ * 3) / result_pool_->hunger_rate_;
    if (step <= 0) return 0;

    return (log2(step));
}

void Node::print() {
    std::cout << "step:" << step_ << " " << game_field_->max_step_ - step_ + game_field_->foods_.num_ - 1 << "pts.\n";
    std::cout << '\n';
    printMap(game_field_, enemies_, *foods_, player_.pos_);
}

void Node::createResult() {
    if (result_pool_->step_log_.size() == 0 || (int) result_pool_->best_step_ > step_ || result_pool_->best_foods_ > foods_->num_) {
        result_pool_->step_log_.clear();
        const Node* node = this;
        while (node != NULL) {
            result_pool_->step_log_.insert(result_pool_->step_log_.begin(), node->partial_step_log_.begin(), node->partial_step_log_.end());
            node = node->parent_;
        }
        print();
        for (std::list<Direction>::iterator p = result_pool_->step_log_.begin(); p != result_pool_->step_log_.end(); p++) {
            switch (*p) {
                case MOVE_UP:
                    std::cout << 'k';
                    break;
                case MOVE_DOWN:
                    std::cout << 'j';
                    break;
                case MOVE_LEFT:
                    std::cout << 'h';
                    break;
                case MOVE_RIGHT:
                    std::cout << 'l';
                    break;
                case MOVE_NONE:
                    std::cout << '.';
                    break;
            }
        }
        std::cout << '\n';
        result_pool_->best_step_ = step_;
        result_pool_->best_foods_ = foods_->num_;
    }
}

int main(int argc, const char **argv) {
    if (argc == 0) exit(EXIT_FAILURE);

    std::srand((unsigned) time(NULL));
    GameField game_field;
    game_field.init(argv[1]);

    ResultPool result_pool(&game_field);

    for (int i = 50; i >= 0; i--) {
        Foods foods(game_field.foods_);

        result_pool.hunger_rate_ = i;
        std::cout << "hunger_rate = " << result_pool.hunger_rate_ << "\n";

        Node root_node(&game_field, &result_pool, &foods);
        root_node.walk();
    }

    exit(EXIT_SUCCESS);
}