#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);
}