//------------------------------------------------------------------------------
/// @file
/// @author ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright (C)HAL Laboratory, Inc.
/// @attention このファイルの利用は、同梱のREADMEにある
/// 利用条件に従ってください。
//------------------------------------------------------------------------------
#include "Answer.hpp"
#define NDEBUG
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
#include <bitset>
#include <functional>
#include <chrono>
#include <cassert>
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define MOD (long long int)(1e9+7)
#define INF (int)(1e9)
#define LINF (long long int)(1e18)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()
typedef std::pair<int, int> Pii;
typedef std::pair<ll, ll> Pll;
#define fast_io ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
//------------------------------------------------------------------------------
namespace hpc {
using namespace std;
constexpr int H = 50, W = 50, N = 50;
int MAKIMONO_V_NUM = 5;
bool full_bitdp = true;
int g = 0;
//Terrain
enum Kind{
//1.0,0.6,0.3,0.1,hoge
A,B,C,D,NONE
};
struct Pos{
float y,x;
Pos(){
y = -1;
x = -1;
}
Pos(float inp_y, float inp_x){
y = inp_y;
x = inp_x;
}
int idx() const{
return (int)y * W + x;
}
float euclid(const Pos& p) const{
return sqrt((p.x-x) * (p.x-x) + (p.y-y) * (p.y-y));
}
Pos operator+ (const Pos& p) const{
return {y + p.y, x + p.x};
}
Pos operator- (const Pos& p) const{
return {y - p.y, x - p.x};
}
bool operator==(const Pos& p) const{
return x == p.x && y == p.y;
}
bool operator!=(const Pos& p) const{
return x != p.x || y != p.y;
}
//mapに突っ込めるようにするために定義
bool operator<(const Pos& p) const{
if(y != p.y){
return y < p.y;
}
return x < p.x;
}
bool inRange() const{
return x >= 0 && x < W && y >= 0 && y < H;
}
};
//------------------------------------------------------------------------------
/// コンストラクタ
/// @detail 最初のステージ開始前に実行したい処理があればここに書きます
Answer::Answer()
{
#if LOCAL
cerr<<fixed<<setprecision(8);
#endif
}
//------------------------------------------------------------------------------
/// デストラクタ
/// @detail 最後のステージ終了後に実行したい処理があればここに書きます
Answer::~Answer()
{
}
Kind terrainToKind(Terrain ter){
if(ter == Terrain::Plain){
return A;
}else if(ter == Terrain::Bush){
return B;
}else if(ter == Terrain::Sand){
return C;
}else if(ter == Terrain::Pond){
return D;
}
return NONE;
}
inline float operator*(float x, Kind k){
if(k == A){
return x;
}else if(k == B){
return x * 0.6f;
}else if(k == C){
return x * 0.3f;
}else if(k == D){
return x * 0.1f;
}
assert(false);
return LINF;
}
inline float operator*(Kind k, float x){
if(k == A){
return x;
}else if(k == B){
return 0.6f * x;
}else if(k == C){
return 0.3f * x;
}else if(k == D){
return 0.1f * x;
}
assert(false);
return LINF;
}
inline float operator/(float x, Kind k){
if(k == A){
return x;
}else if(k == B){
return x / 0.6f;
}else if(k == C){
return x / 0.3f;
}else if(k == D){
return x / 0.1f;
}
return LINF;
}
inline double operator*(double x, Kind k){
if(k == A){
return x;
}else if(k == B){
return x * 0.6;
}else if(k == C){
return x * 0.3;
}else if(k == D){
return x * 0.1;
}
assert(false);
return LINF;
}
inline double operator*(Kind k, double x){
if(k == A){
return x;
}else if(k == B){
return 0.6 * x;
}else if(k == C){
return 0.3 * x;
}else if(k == D){
return 0.1 * x;
}
assert(false);
return LINF;
}
inline double operator/(double x, Kind k){
if(k == A){
return x;
}else if(k == B){
return x / 0.6;
}else if(k == C){
return x / 0.3;
}else if(k == D){
return x / 0.1;
}
return LINF;
}
inline float euclid(float y, float x, float yy, float xx){
return sqrt((y-yy)*(y-yy) + (x-xx)*(x-xx));
}
//巻物のpos ただしM.back()はスタート地点
vector<Pos> M;
//巻物の個数
int m;
//start地点
Pos S;
//そのステージにおいて出力する予定のpos
vector<Pos> plan;
//次にgetTargetPos()で呼び出されたときに, 作成したplanの何番目を返せばいいかを管理
int plan_idx;
//辿る順番に頂点のidを格納
vector<int> answer;
//kind_map[y*W + x]: (x,y)のTerrain
vector<Kind> kind_map;
//i番目の頂点のpos
vector<Pos> gToPos;
//角として加わった頂点の個数
int kadoNum;
//擬距離行列
vector<vector<double>> dist_matrix;
//ワーシャルフロイド後に復元する用
vector<vector<int>> next_for_restoration;
//(x,y)のTerrainを返す
inline Kind kind(float y, float x){
assert(y>=0);
assert(y<N);
if(x<0){
cerr<<y<<" "<<x<<endl;
}
assert(x>=0);
assert(x<N);
return kind_map[static_cast<int>(y) * W + static_cast<int>(x)];
}
inline Kind kind(const Pos& p){
return kind(p.y, p.x);
}
// 地形を考慮して(x,y)から(xx,yy)までの距離を計算
double calc_dist(double y, double x, double yy, double xx){
//各マス目ごとに距離を足していく
double sum = 0;
//途中でジャンプする場合にかかるとみなす手数
//色々試したが大差ない
constexpr float JUMP_RATE = 1.5;
//良いterrainからの最初のジャンプを考慮したい
//周囲のterrainのうち最も良いものを求める
Kind best_kind = kind(y,x);
if((double)(int)y == y && y != 0){
chmin(best_kind, kind(y-0.1, x));
}
if((double)(int)x == x && x != 0){
chmin(best_kind, kind(y, x-0.1));
}
if((double)(int)y == y && y != 0 && (double)(int)x == x && x != 0){
chmin(best_kind, kind(y-0.1, x-0.1));
}
//1手で到達できる場合
//返り値を1.0とするのも試したが, 大差ない
if(euclid(y,x,yy,xx) <= 1.0f * best_kind){
return euclid(y,x,yy,xx) / best_kind;
}
double dy = yy - y;
double dx = xx - x;
//最初のterrainを利用して1歩進む
{
double r = euclid(dy,dx,0,0);
y += dy / r * best_kind;
x += dx / r * best_kind;
sum += 1;
}
const float eps = 1e-5;
//真横に移動する場合
if(dy == 0){
double now_x = x;
while(abs(now_x - xx) > 1){
double next = (dx > 0 ? (int)now_x + 1 + eps : (int)now_x - eps);
//(2,3)から(10,3)に移動する場合などは
//y座標を3にしたほうがいい場合と3-epsにしたほうがいい場合がある
//この考慮のために, 真横移動と真縦移動だけ場合分けしている
Kind k = min(kind(y + eps, now_x), kind(y - eps, now_x));
sum += abs(next - now_x) / k;
now_x = next;
}
double next = xx;
Kind k = min(kind(y, now_x), kind(y - eps, now_x));
sum += abs(next - now_x) / k;
assert(sum > 0);
return sum;
}
//真縦に移動する場合
if(dx == 0){
double now_y = y;
while(abs(now_y - yy) > 1){
double next = (dy > 0 ? (int)now_y + 1 + eps : (int)now_y - eps);
Kind k = min(kind(now_y, x + eps), kind(now_y, x - eps));
sum += abs(next - now_y) / k;
now_y = next;
}
double next = yy;
Kind k = min(kind(now_y, x + eps), kind(now_y, x - eps));
sum += abs(next - now_y) / k;
assert(sum > 0);
return sum;
}
Kind before_k = kind(y,x);
while(true){
dy = yy - y;
dx = xx - x;
//目的地に十分近づいたら終了
//これが終了条件として正しいかどうかはかなり怪しいが,
//動いているのでヨシ(よくない)
if(((int)y == (int)yy && (int)x == (int)xx) || (abs(y-yy) < 1e-4f && abs(x-xx) < 1e-4f)){
sum += euclid(y,x,yy,xx) / kind(y,x);
break;
}
double keisu = INF;
Kind k = kind(y,x);
//直前のterrainの方が良い場合は, それを利用してジャンプ
if(k > before_k){
//一手以内で到着可能な場合
if(euclid(y,x,yy,xx) < 1.0f * before_k){
sum += euclid(y,x,yy,xx) / before_k;
assert(sum > 0);
return sum;
}
//到着できない場合はジャンプ
double r = euclid(dy,dx,0,0);
y += dy / r * before_k;
x += dx / r * before_k;
before_k = k;
sum += 1.0f * JUMP_RATE;
continue;
}
assert(dy != 0);
assert(dx != 0);
//次のマスに移動したいので
//xまたはyが整数をギリギリまたぐようにする
chmin(keisu, ((int)y + (dy > 0 ? 1 : 0) - y) / dy);
chmin(keisu, ((int)x + (dx > 0 ? 1 : 0) - x) / dx);
assert(keisu != INF);
sum += keisu * sqrt(dy*dy + dx*dx) / k;
y = y + keisu * dy + (dy > 0 ? 1 : -1) * eps;
x = x + keisu * dx + (dx > 0 ? 1 : -1) * eps;
before_k = k;
}
assert(sum > 0);
return sum;
}
//巻物や初期地点のほかに, 経由点として有望な頂点を追加した上で
//任意の2頂点について直接向かった場合の擬距離をcalc_dist()で求めた後,
//ワーシャルフロイド法によって, 経由点を考慮した場合の2頂点間の最短擬距離を求める
void init_graph(){
//初期化
kadoNum = 0;
gToPos.clear();
plan.clear();
//追加済みの頂点の重複追加を防止
set<Pos> added;
reps(y,N-1){
reps(x,N-1){
//周囲4マスのterrainの個数を数える
int count[4] = {};
count[kind(y,x)]++;
count[kind(y,x-1)]++;
count[kind(y-1,x)]++;
count[kind(y-1,x-1)]++;
//周囲4マスに登場しないterrainの種類数
int zero_count = 0;
rep(i,4){
zero_count += count[i] == 0;
}
//周囲に1種類しかない場合は経由する意味がない
if(zero_count == 3) continue;
//周囲に2種類あって, それぞれ2個ずつあり, それらが隣り合ってる場合も
//経由する必要がない
if(zero_count == 2 && kind(y,x) != kind(y-1, x-1) && kind(y-1,x) != kind(y,x-1)) continue;
Pos p = {(float)y, (float)x};
gToPos.push_back(p);
added.insert(p);
kadoNum++;
}
}
if(m<=13){
//後にbitDPをする際に,
//各巻物を踏む地点の候補を
//マスの中心 + マスの角とする
MAKIMONO_V_NUM = 5;
full_bitdp = true;
}else{
MAKIMONO_V_NUM = 1;
full_bitdp = true;
}
//巻物と初期位置をグラフとして追加
rep(i,M.size()){
float y = M[i].y;
float x = M[i].x;
assert(Pos(y,x).inRange());
if(i != (int)M.size() - 1 && MAKIMONO_V_NUM >= 4){
//巻物のマスの角4つを追加
for(float eps_y : {0.0f, 0.99998f}){
for(float eps_x : {0.0f, 0.99998f}){
gToPos.push_back({(int)y+eps_y, (int)x+eps_x});
if(gToPos.back().y <= 0.8 || gToPos.back().x <= 0.8 || gToPos.back().y >= N - 0.8 || gToPos.back().x >= N-0.8){
//ステージギリギリの点は考慮する必要がないかつ扱いが面倒なので頂点としては追加しない
//その代わりにダミー(中心と一致)を追加しておく(すでに追加した頂点と重複するが問題はないはず)
//後の実装の都合上, MAKIMONO_V_NUMの個数分を必ず追加しないと行けないので.
gToPos.back() = {y,x};
}
}
}
}
if(MAKIMONO_V_NUM == 1 || MAKIMONO_V_NUM == 5 || i == (int)M.size() - 1){
gToPos.push_back({y,x});
added.insert(gToPos.back());
}
}
//初期位置の角と辺の8マスも追加
for(float eps_y : {-0.5f, 0.0f, 0.5f}){
for(float eps_x : {-0.5f, 0.0f, 0.5f}){
const Pos p = S + Pos(eps_y, eps_x);
if(p.y <= 0.1 || p.x <= 0.1 || p.y >= N-0.1 || p.x >= N-0.1) continue;
if(added.count(p) > 0) continue;
gToPos.push_back(p);
added.insert(p);
}
}
//巻物または初期位置から, 真横または真縦に移動した結果
//良いterrainに抜けられるなら, その境界を頂点として追加
rep(i,M.size()){
for(Pii delta : {Pii{-1,0}, {1,0}, {0,-1}, {0,1}}){
int dy = delta.first;
int dx = delta.second;
int y = M[i].y;
int x = M[i].x;
//初期位置の場合は一歩進んだ場所からスタート
//(初期位置が1マスのみの平地のパターンを考慮)
if(i == M.size() - 1){
y += dy;
x += dx;
if(!Pos(y,x).inRange()) continue;
}
Kind base_k = kind(y,x);
while(y >= 1 && y <= N-1 && x >= 1 && x <= N-1){
Kind k = kind(y,x);
//異なる地形に抜けた
if(base_k != k){
//より良い地形になっている場合は境界を頂点として追加
if(k < base_k){
//p1: 境界の中心
//p2,p3: 境界の端
//例: (7.5,5.5)が巻物かつ池, (8.5,5.5), (9.5,5.5)が池, (10.5, 5.5)が平地の場合
//p1: (10, 5.5)
//p2: (10, 5)
//p3: (10, 6)
Pos p1, p2, p3;
if(dy == -1){
p1 = {y + 1.0f, x + 0.5f};
p2 = {y + 1.0f, (float)x};
p3 = {y + 1.0f, x + 1.0f};
}
if(dy == 1){
p1 = {(float)y, x + 0.5f};
p2 = {(float)y, (float)x};
p3 = {(float)y, x + 1.0f};
}
if(dx == -1){
p1 = {y + 0.5f, x + 1.0f};
p2 = {(float)y, x + 1.0f};
p3 = {y + 1.0f, x + 1.0f};
}
if(dx == 1){
p1 = {y + 0.5f, (float)x};
p2 = {(float)y, (float)x};
p3 = {y + 1.0f, (float)x};
}
if(added.count(p1) == 0 && p1.inRange()){
added.insert(p1);
gToPos.push_back(p1);
}
if(added.count(p2) == 0 && p2.inRange()){
added.insert(p2);
gToPos.push_back(p2);
}
if(added.count(p3) == 0 && p3.inRange()){
added.insert(p3);
gToPos.push_back(p3);
}
}
//地形が改善していてもしていなくても, 最初に変化した場所で打ち切り
break;
}
y += dy;
x += dx;
}
}
}
//dist_matrix[i][j]:= gToPos[i]からgToPos[j]への擬距離
dist_matrix = vector<vector<double>>(gToPos.size(), vector<double>(gToPos.size(), INF));
//ワーシャルフロイドの復元用の配列
next_for_restoration = vector<vector<int>>(gToPos.size(), vector<int>(gToPos.size(), -1));
rep(i,gToPos.size()){
rep(j,gToPos.size()){
if(i == j) continue;
const Pos& from = gToPos[i];
const Pos& to = gToPos[j];
double dist = calc_dist(from.y, from.x, to.y, to.x);
//ワーシャルフロイドするために初期化
dist_matrix[i][j] = dist;
next_for_restoration[i][j] = j;
}
dist_matrix[i][i] = 0;
}
//ワーシャルフロイド
rep(k,gToPos.size()){
rep(i,gToPos.size()){
rep(j,gToPos.size()){
if(dist_matrix[i][j] > dist_matrix[i][k] + dist_matrix[k][j]){
dist_matrix[i][j] = dist_matrix[i][k] + dist_matrix[k][j];
next_for_restoration[i][j] = next_for_restoration[i][k];
}
}
}
}
}
//powerを考慮して, nowからtoに向かって動く場合に移動可能な最大量(dx,dy)を返す
Pos calc_max_dy_dx(const Pos& now, const Pos& to, float power){
assert(now.inRange());
Kind k = kind(now.y, now.x);
float maxlen = power * k;
float dy = to.y - now.y;
float dx = to.x - now.x;
float r = euclid(dy,dx,0.0f,0.0f);
if(r > maxlen){
dy *= (maxlen / r);
dx *= (maxlen / r);
//誤差を懸念して少し小さめに調整
dy *= 0.99998f;
dx *= 0.99998f;
}
return {dy,dx};
}
//pや, pを少しずらした地点のうち, 最も良い地形を返す
Kind best_arround_kind(const Pos& p){
assert(p.inRange());
Kind best_kind = kind(p);
for(float eps_y : {-0.01f, 0.01f}){
for(float eps_x : {-0.01f, 0.01f}){
Pos arround_p = {p.y + eps_y, p.x + eps_x};
if(!arround_p.inRange()) continue;
Kind k = kind(p.y + eps_y, p.x + eps_x);
chmin(best_kind, k);
}
}
return best_kind;
}
//nowからtoに1手で届くかどうか
bool canReachable(const Pos& now, const Pos& to, float power){
assert(now.inRange());
Kind k = kind(now.y, now.x);
float maxlen = k * power;
float r = euclid(now.y, now.x, to.y, to.x);
//誤差を懸念して余裕をもたせて判定
return (r < maxlen * 0.99998f);
}
struct State{
//現在地, 次の目的地
Pos now, next;
//次の目的地のpoints[]におけるidx
int next_i;
//次の目的地までの普通のユークリッド距離
float dist;
float power;
//ログ復元用
int before_li;
//真縦移動または真横移動を探索中の状態を保護するためのもの
int dy = 0, dx = 0;
};
//次の状態の候補next_sを用いてmp1を更新する(mp1はdp配列のようなもの)
//mp1: {目的地, 真縦移動または真横移動を行ったかどうか, 移動後の地形}に着目し,
// この3点が一致する状態については, 最も目的地へのユークリッド距離が小さいもののみを保存している
void update(vector<std::map<pair<Pos,bool>, State>>& mp1, State next_s){
const Pos& next_p = next_s.next;
//keyはpair<目的地,真縦移動または真横移動を行ったかどうか>
pair<Pos, bool> key = {next_p, next_s.dy != 0 || next_s.dx != 0};
assert(next_s.now.inRange());
const Kind next_k = kind(next_s.now.y, next_s.now.x);
if(mp1[next_k].count(key) == 0){
//3点が一致する要素が存在しないなら保存
mp1[next_k][key] = next_s;
}else{
//目指してる目的地が同じだけど, 先に進んでいる場合(2度同じ地点を通る場合など)
if(mp1[next_k][key].next_i < next_s.next_i){
mp1[next_k][key] = next_s;
}else if(mp1[next_k][key].next_i == next_s.next_i){
//目指してる目的地が一緒の場合は, 目的地により近い場合
if(mp1[next_k][key].dist > next_s.dist){
mp1[next_k][key] = next_s;
}
}
}
}
//initializeで呼ばれる
//そのステージで出力するPosを全てplanに突っ込む
//ワーシャルフロイドによって各巻物間の擬距離がわかっているため,
//それを元にbitDPを行う
//ワーシャルフロイドの復元用配列next_for_restoration[]を用いて,
//巻物以外(地形の角など)も含めた巡る順番をpointsに突っ込む
//その後, dpをしてplanを求める
void planning(){
plan.clear();
//ワーシャルフロイドの対象となっていた頂点を, 巡るべき順番に突っ込んでいく
vector<Pos> Vs;
//V_isMakimono[i]:= Vs[i]が巻物かどうか
vector<bool> V_isMakimono;
//初期地点を追加
Vs.push_back(gToPos[m * MAKIMONO_V_NUM + kadoNum]);
V_isMakimono.push_back(false);
//ワーシャルフロイドから復元する
{
int now = m * MAKIMONO_V_NUM + kadoNum;
rep(i,answer.size()){
//次に向かうべき巻物
int to = answer[i] + kadoNum;
while(true){
//復元
now = next_for_restoration[now][to];
if(now == to) break;
Vs.push_back(gToPos[now]);
V_isMakimono.push_back(false);
}
Vs.push_back(gToPos[to]);
V_isMakimono.push_back(true);
now = to;
}
}
//巡る頂点とその次に巡る頂点の間に地形の変化がある場合はその境界線上の1点を追加する
//良い地形から悪い地形に変化する場合に,
//境界ギリギリに着地した後ジャンプしたほうが強い場合が多々あるが,
//そのために本来動けるはずだった分を無駄にしたくない
//後々の実装で, 巡る各点を少しずらした点も目的地として設定しdpを行うので,
//その対象に加えるのが狙い.
//Vsの要素に, 境界線上の点を加えたもの
vector<Pos> points;
points.reserve(Vs.size());
//points[i]が巻物かどうか
vector<bool> isMakimono;
isMakimono.reserve(V_isMakimono.size());
rep(i,Vs.size()){
Pos from_base;
if(i == 0){
from_base = M.back();
}else{
from_base = Vs[i-1];
}
Pos to_base = Vs[i];
//真縦または真横移動の場合は, 悪い地形があったとしても真縦または真横に移動してくれるので, 考慮する必要がない
if(abs(from_base.y - to_base.y) < 0.0001f || abs(from_base.x - to_base.x) < 0.0001f){
points.push_back(to_base);
isMakimono.push_back(V_isMakimono[i]);
continue;
}
//近い場合も考慮しない
if(from_base.euclid(to_base) < 2){
points.push_back(to_base);
isMakimono.push_back(V_isMakimono[i]);
continue;
}
//nowからtoを結ぶ線分上の境界を見ていく
Pos now = from_base;
Pos to = to_base;
//to側(線分の内側)にずらす
if(i != 0){
now.y += (to.y > now.y ? 0.00002f : -0.00002f);
now.x += (to.x > now.x ? 0.00002f : -0.00002f);
}
//now側にずらす
to.y += (to.y > now.y ? -0.00002f : 0.00002f);
to.x += (to.x > now.x ? -0.00002f : 0.00002f);
assert(now.inRange());
assert(to.inRange());
float y = now.y, x = now.x, yy = to.y, xx = to.x;
int before_int_y = (int)y;
int before_int_x = (int)x;
//nowからtoに向かう間に, 悪い地形に変化した場合は, その点をiriguchiとして保存
Pos iriguchi = {-1,-1};
Kind before_k = kind(y,x);
constexpr float eps = 1e-5;
while(true){
//toに到着したかどうかを判定
//動いてるからヨシ(よくない)
if(((int)y == (int)yy && (int)x == (int)xx) || (abs(y-yy) < 1e-4f && abs(x-xx) < 1e-4f)){
break;
}
assert(Pos(y,x).inRange());
Kind k = kind(y,x);
if(before_k > k){
//悪い地形から良い地形に抜ける:出口
Pos deguchi = {y, x};
if(before_int_y != (int)y){
//縦に動いた結果地形が変化した場合
deguchi.y = max(before_int_y, (int)y);
assert(deguchi.inRange());
}
if(before_int_x != (int)x){
//横に動いた結果地形が変化した場合
deguchi.x = max(before_int_x, (int)x);
assert(deguchi.inRange());
}
if(iriguchi.y != -1 && deguchi.y != -1){
//悪い地形に入って, 良い地形に抜けた
if(((float)(int)iriguchi.y == iriguchi.y) == ((float)(int)deguchi.y == deguchi.y)){
//iriguchiのyが整数かどうか == deguchiのyが整数かどうか
//すなわち, 縦に抜けていくまたは横に抜けていく
//その場合は境界上のどの点に点を打つかについては
//入り口と出口の中間とする
if((float)(int)iriguchi.y == iriguchi.y){
//yが境界線
float mannaka_x = (iriguchi.x + deguchi.x) / 2;
points.push_back({iriguchi.y, mannaka_x});
points.push_back({deguchi.y, mannaka_x});
}else{
//xが境界線
float mannaka_y = (iriguchi.y + deguchi.y) / 2;
points.push_back({mannaka_y, iriguchi.x});
points.push_back({mannaka_y, deguchi.x});
}
isMakimono.push_back(false);
isMakimono.push_back(false);
assert(points.back().inRange());
}else{
//斜めに抜けるパターン
//素直に点を追加
points.push_back(iriguchi);
points.push_back(deguchi);
isMakimono.push_back(false);
isMakimono.push_back(false);
}
//リセット
iriguchi = {-1,-1};
deguchi = {-1,-1};
}
//Todo: 良い地形→やや悪い地形→悪い地形→良い地形のパターン
}else if(before_k < k){
//悪い地形に入る: 入り口としてメモ
if(Pos(y+(yy-y > 0 ? -1 : 1), x).inRange() && kind(y,x) != kind(y+(yy-y > 0 ? -1 : 1), x)){
iriguchi = {(float)((int)y + (yy-y > 0 ? 0 : 1)), x};
assert(iriguchi.inRange());
}else if(Pos(y, x+(xx-x > 0 ? -1 : 1)).inRange() && kind(y,x) != kind(y, x+(xx-x > 0 ? -1 : 1))){
iriguchi = {y, (float)((int)x + (xx-x > 0 ? 0 : 1))};
assert(iriguchi.inRange());
}
}
const float dy = yy - y;
const float dx = xx - x;
//次のマス目に移動
double keisu = INF;
assert(dy != 0);
assert(dx != 0);
chmin(keisu, ((int)y + (dy > 0 ? 1 : 0) - y) / dy);
chmin(keisu, ((int)x + (dx > 0 ? 1 : 0) - x) / dx);
assert(keisu != INF);
assert(Pos(y,x).inRange());
before_k = kind(y,x);
before_int_y = (int)y;
before_int_x = (int)x;
y = y + keisu * dy + (dy > 0 ? 1 : -1) * eps;
x = x + keisu * dx + (dx > 0 ? 1 : -1) * eps;
}
//本来の目的地を追加
points.push_back(to_base);
isMakimono.push_back(V_isMakimono[i]);
}
//pointsの各要素について, そのpointだけでなく
//少しずらした位置も候補とする
vector<vector<Pos>> to_list(points.size());
rep(i,points.size()){
const Pos& target = points[i];
if(isMakimono[i]){
//巻物の場合
to_list[i].reserve(49);
assert(i >= 1);
if(i + 1 == points.size()){
//最終地点だったら9*9通り全て試すようにする
for(float eps_y : {0.0f, 0.125f, 0.25f, 0.375f, 0.5f, 0.625f, 0.75f, 0.875f, 0.99998f}){
for(float eps_x : {0.0f, 0.125f, 0.25f, 0.375f, 0.5f, 0.625f, 0.75f, 0.875f, 0.99998f}){
to_list[i].push_back({(int)target.y + eps_y, (int)target.x + eps_x});
}
}
}else if(points[i-1] == points[i+1]){
//境界→悪い地形に有る巻物→境界 という動きをする場合
//巻物のマスの辺上の点を候補とする
set<Pos> koho;
if(points[i-1].y < target.y){
//境界→巻物へ向かう際にy軸性の方向に移動するならば,
//巻物のマスの上辺に点を生成
for(float eps : {0.0f, 0.125f, 0.25f, 0.375f, 0.5f, 0.675f, 0.75f, 0.825f, 0.99998f}){
koho.insert({(float)(int)target.y, (int)target.x + eps});
}
}
if(points[i-1].y > target.y){
for(float eps : {0.0f, 0.125f, 0.25f, 0.375f, 0.5f, 0.675f, 0.75f, 0.825f, 0.99998f}){
koho.insert({(float)(int)target.y + 0.9998f, (int)target.x + eps});
}
}
if(points[i-1].x < target.x){
for(float eps : {0.0f, 0.125f, 0.25f, 0.375f, 0.5f, 0.675f, 0.75f, 0.825f, 0.99998f}){
koho.insert({(int)target.y + eps, (float)(int)target.x});
}
}
if(points[i-1].x > target.x){
for(float eps : {0.0f, 0.125f, 0.25f, 0.375f, 0.5f, 0.675f, 0.75f, 0.825f, 0.99998f}){
koho.insert({(int)target.y + eps, (float)(int)target.x + 0.9998f});
}
}
for(auto p : koho){
//ステージ領域の辺上の点は省く
if(p.y <= 0.1 || p.x <= 0.1 || p.y >= N-0.1 || p.x >= N-0.1) continue;
to_list[i].push_back(p);
}
}else{
//巻物を踏む地点の候補pを決める
//「prev地点からpまでのeuclid距離」と「pからnext地点までのeuclid距離」の2目的について
//パレート最適になるような点pのみを候補とする
//Todo: 前後も巻物の場合は特別扱いしたほうがいいかも
//koho:= pair<pair<dist(prev,x), dist(x,next)>, 経由点p>
vector<pair<pair<double,double>,Pos>> koho;
for(float eps_y : {0.0f, 0.125f, 0.25f, 0.375f, 0.5f, 0.675f, 0.75f, 0.875f, 0.99998f}){
for(float eps_x : {0.0f, 0.125f, 0.25f, 0.375f, 0.5f, 0.675f, 0.75f, 0.875f, 0.99998f}){
//eps_y,xの候補を9->5に減らすと 26悪化
// for(float eps_y : {0.0f, 0.25f, 0.5f, 0.75f, 0.99998f}){
// for(float eps_x : {0.0f, 0.25f, 0.5f, 0.75f, 0.99998f}){
const Pos p = {(int)target.y + eps_y, (int)target.x + eps_x};
double prev_dist = p.euclid(points[i-1]);
double next_dist = p.euclid(points[i+1]);
koho.push_back({{prev_dist, next_dist}, p});
}
}
sort(all(koho));
double min_next_dist = INF;
rep(j,koho.size()){
//ソートされてるのでprev_distはkoho[<j]よりも大きい
//next_distが大きいなら過去の点に優越されているので除外
if(min_next_dist <= koho[j].first.second) continue;
min_next_dist = koho[j].first.second;
to_list[i].push_back(koho[j].second);
}
}
}else if(((int)target.y == target.y) ^ ((int)target.x == target.x)){
//xまたはyのどちらかが整数
//すなわち境界線上にある場合
//境界線上の, 少しずらした点を追加する
assert(target.inRange());
Kind base_k = best_arround_kind(target);
for(float eps : {0.0f,0.25f,0.44448f,1.0f,2.0f,-0.25f,-0.5f,-1.0f,-2.0f,0.75f,-0.75f,1.5f,-1.5f,3.0f,-3.0f}){
float y = target.y;
float x = target.x;
if((int)y == y){
//yが境界線上にあるならxをずらす
x = x + eps;
}else{
//xが境界線上にあるならyをずらす
y = y + eps;
}
if(!Pos(y,x).inRange()) continue;
//地形が悪くなるような点は追加しない
if(base_k < best_arround_kind(Pos(y,x))) continue;
to_list[i].push_back({y,x});
}
}else if(target == M.back()){
//スタート地点
//追加しなくても良いはずだが一応
to_list[i].push_back(M.back());
}else{
//地形の角の場合
assert(target.inRange());
Kind base_k = best_arround_kind(target);
//地形が悪くなるようなずらし方はしない
//15点落ちてる
for(float eps : {-0.99998f, -0.5f, 0.5f, 0.99998f, -0.25f,0.25f,0.75f,-0.75f,1.5f,-1.5f,2.0f,-2.0f}){
to_list[i].push_back({target.y + eps, target.x});
if(!to_list[i].back().inRange() || best_arround_kind(to_list[i].back()) > base_k) to_list[i].pop_back();
to_list[i].push_back({target.y, target.x + eps});
if(!to_list[i].back().inRange() || best_arround_kind(to_list[i].back()) > base_k) to_list[i].pop_back();
}
//元の点
to_list[i].push_back(target);
}
}
//qの各状態について, 1ターン動いた状態を列挙し
//似た状態については枝刈りしつつ, 残ったものをqに突っ込む
//を繰り返す
queue<State> q;
State first_s;
first_s.now = points[0];
first_s.next = points[0];
first_s.next_i = 0;
first_s.dist = 0;
first_s.power = 1.0f;
first_s.before_li = -1;
q.push(first_s);
//復元用
vector<State> logs;
while(true){
//mp1: 状態の現在の地形からmp2に飛ばす
//mp2: (次の目的地, 真縦移動または真横移動を行ったかどうか)から最良状態に飛ばす
vector<std::map<pair<Pos,bool>, State>> mp1(4);
//最後の巻物に到着したらtrueにして, whileループを脱出
bool arrived = false;
while(q.size() > 0){
//q内の各状態sについて見ていく
const auto& s = q.front(); q.pop();
//復元用
int before_idx = logs.size();
logs.push_back(s);
//終了
if(s.next_i == points.size()){
arrived = true;
break;
}
const Pos& now = s.now;
const int next_i = s.next_i;
const float power = s.power;
//目指している場所
const Pos& to_honrai = s.next;
if(canReachable(now, to_honrai, power)){
//目指している場所に到達可能な場合
//その次を考えて行動する
//コードの後の行で,
//target_iに到達できるなら, その次をtarget_iとして, 到達できるか考えて,
//それも到達できるなら...
//と先を考えていく
int target_i = next_i;
while(true){
//whileを脱する条件は後述
//target_iに対応する, 少しずらした点たちについて,
//到達できる点が一つ以上あるかどうか
bool reachable = false;
rep(i, to_list[target_i].size()){
//最初は本来の目的地だけでOK
//その次以降を考える場合は, ずらした点候補全てについて考える
//8しか変わらない
if(target_i == next_i && i != 0) break;
const Pos& to = (target_i == next_i ? to_honrai : to_list[target_i][i]);
//届かないなら飛ばす
if(!canReachable(now, to, power)) continue;
reachable = true;
//最後の巻物なら適当に着地しておしまい
if(target_i + 1 == points.size()){
const Pos dif = {to.y - now.y, to.x - now.x};
State next_s;
next_s.now = now + dif;
if(!next_s.now.inRange()) continue;
next_s.next_i = target_i + 1;
next_s.power = s.power * (isMakimono[target_i] ? 1.1f : 1.0f);
next_s.next = {-1,-1};
next_s.dist = next_s.now.euclid(next_s.next);
next_s.before_li = before_idx;
update(mp1, next_s);
break;
}
//行き先が巻物ならそこに着地
if(isMakimono[target_i]){
const Pos dif = {to.y - now.y, to.x - now.x};
State next_s;
next_s.now = now + dif;
next_s.next_i = target_i + 1;
next_s.power = s.power * 1.1f;
next_s.before_li = before_idx;
for(auto& next_to : to_list[target_i + 1]){
next_s.next = next_to;
next_s.dist = next_s.now.euclid(next_s.next);
update(mp1, next_s);
}
continue;
}
//巻物でない場合は,
//target_iの(ずらした各)点と, 本来向かうはずだった点との線分上の点を試す
//target_iの(ずらした各)点と, 現在の点との線分上の点も試す
for(const Pos& next_next : to_list[target_i + 1]){
assert(s.now.inRange());
const float maxlen = s.power * kind(s.now.y, s.now.x);
const float r = maxlen * 0.99990f;
//toからの線分上とnowからの線分上どちらも試す
for(Pos from_pos : {to, now}){
//到達可能
float ok_y = from_pos.y, ok_x = from_pos.x;
//到達不可能(可能な場合もあるが)
float ng_y = next_next.y, ng_x = next_next.x;
//二分探索
while(euclid(ok_y,ok_x,ng_y,ng_x) > 0.00005f && !(ok_y==ng_y && ok_x==ng_x)){
const float mid_y = (ok_y + ng_y) / 2;
const float mid_x = (ok_x + ng_x) / 2;
if(euclid(mid_y,mid_x,now.y,now.x) <= r){
ok_y = mid_y;
ok_x = mid_x;
}else{
ng_y = mid_y;
ng_x = mid_x;
}
}
//到達可能な点に移動するパターンだけでなく,
//それよりも手前に移動するパターンも考慮
//する予定だったが, 実行時間を削った関係で2通りしか試していない
const int bunkatsu = 20;
REP(per, bunkatsu + 2){
//移動可能距離 * per/bunkatsuだけ移動する
//per == bunkatsu+1のときは例外
float to_y, to_x;
if(per == bunkatsu + 1){
//from_posがtoすなわち本来の目的地だった場合,
//ok側に行かず, toの手前を踏んだ結果いい地形を引く可能性がある
to_y = from_pos.y * (1.0f + 0.00005f) + ok_y * (-0.00005f);
to_x = from_pos.x * (1.0f + 0.00005f) + ok_x * (-0.00005f);
}else{
//移動可能距離 * per/bunkatsuだけ移動する
to_y = ok_y * ((float)per / bunkatsu) + from_pos.y * (1.0f - (float)per / bunkatsu);
to_x = ok_x * ((float)per / bunkatsu) + from_pos.x * (1.0f - (float)per / bunkatsu);
}
const Pos dif = {to_y - now.y, to_x - now.x};
//少しずらした点も考慮(良い地形を踏む可能性)
for(float eps_y : {-0.1f, 0.0f, 0.1f}){
for(float eps_x : {-0.1f, 0.0f, 0.1f}){
State next_s;
next_s.now = now + Pos(dif.y + eps_y, dif.x + eps_x);
next_s.now = now + calc_max_dy_dx(now, next_s.now, s.power);
if(!next_s.now.inRange()) continue;
next_s.next = next_next;
next_s.next_i = target_i + 1;
next_s.power = s.power;
next_s.dist = next_next.euclid(next_s.now);
next_s.before_li = before_idx;
update(mp1, next_s);
}
}
//境界に点が打てていないと困りそう
if(per != bunkatsu + 1) break;
}
}
}
assert(!isMakimono[target_i]);
//境界線であるならば, 境界線上の点を試す
if(((int)to.y != to.y) ^ ((int)to.x != to.x)){
//(bx,by)から(by,ey)の範囲を試す
float bx,ex,by,ey;
if((int)to.y == to.y){
//yが整数
bx = (int)to.x;
ex = bx + 1;
by = (int)to.y;
if(Pos(by - 0.00005f, to.x).inRange() && kind(by - 0.00005f, to.x) < kind(by, to.x)){
//少し負の方向にずらしたほうが地形が改善する場合はずらす
by = by - 0.00005f;
}
ey = by;
}else{
//xが整数
by = (int)to.y;
ey = by + 1;
bx = (int)to.x;
if(Pos(to.y, bx - 0.00005f).inRange() && kind(to.y, bx - 0.00005f) < kind(to.y, bx)){
//少し負の方向にずらしたほうが地形が改善する場合はずらす
bx = bx - 0.00005f;
}
ex = bx;
}
for(const Pos& next_next : to_list[target_i + 1]){
const int bunkatsu = 8;
rep(per, bunkatsu + 1){
//(bx,by)から(by,ey)の間に点を追加
const float to_y = by + (ey - by) * ((float)per / bunkatsu);
const float to_x = bx + (ex - bx) * ((float)per / bunkatsu);
// if(!canReachable(now, Pos(to_y, to_x), power)) break;
State next_s;
const Pos dif = {to_y - now.y, to_x - now.x};
next_s.now = now + Pos(dif.y, dif.x);
next_s.now = now + calc_max_dy_dx(now, next_s.now, s.power);
if(!next_s.now.inRange()) continue;
next_s.next = next_next;
next_s.next_i = target_i + 1;
next_s.power = s.power;
next_s.dist = next_next.euclid(next_s.now);
next_s.before_li = before_idx;
update(mp1, next_s);
}
}
}
}
//巻物なら終わり
if(isMakimono[target_i]) break;
//次がなければ終わり
if(target_i + 1 == points.size()) break;
//一個も到達できてなければ終わり
if(!reachable) break;
//そうでなければその次を考える
target_i++;
}
continue;
}//canReachble(now, to_honrai, power)
const Pos& to = to_honrai;
//目的地点に到達不可能な場合
const int bunkatsu = 5;
//nowからtoへ向かう, 可能な最大の移動
const Pos dyx_base_base = calc_max_dy_dx(now, to, power);
REPS(per, bunkatsu){
//最大移動可能距離 * per/bunkatsuだけ移動
//少しずらす
Pos EPS_POS_LIST[] = {
{0.0f, 0.0f}, {0.0f, 0.1f}, {0.0f, -0.1f}, {0.1f, 0.0f}, {-0.1f, 0.0f},
{0.1f, -0.1f}, {-0.1f, 0.1f}, {-0.1f, -0.1f}, {0.1f, 0.1f},
{0.0f, -3.0f}, {0.0f, 3.0f}, {3.0f, 0.0f}, {-3.0f, 0.0f},
{3.0f,3.0f}, {-3.0f,-3.0f},{3.0f,-3.0f}, {-3.0f,3.0f}
};
for(Pos eps_pos : EPS_POS_LIST){
const float eps_y = eps_pos.y;
const float eps_x = eps_pos.x;
//eps_posだけ方向をずらし, 移動量がオーバーしてたら修正
const Pos dyx_base = calc_max_dy_dx(now, now + dyx_base_base + Pos(eps_y, eps_x), power);
//per/bunkatsu倍する 手前に移動することでいい地形を踏む可能性を考慮
const Pos dyx = {dyx_base.y * ((float)per / bunkatsu), dyx_base.x * ((float)per / bunkatsu)};
State next_s;
next_s.before_li = before_idx;
next_s.now = now + dyx;
next_s.next = to;
next_s.next_i = next_i;
next_s.power = s.power;
if(!next_s.now.inRange()) continue;
//目的地までのユークリッド距離
next_s.dist = next_s.now.euclid(next_s.next);
update(mp1, next_s);
}
}
//真縦移動または真横移動を行う
for(Pos delta : {Pos(-100,0),Pos(100,0),Pos(0,-100),Pos(0,100)}){
State next_s;
const Pos dyx = calc_max_dy_dx(now, now + delta, power);
next_s.now = now + dyx;
if(!next_s.now.inRange()) continue;
next_s.before_li = before_idx;
next_s.next = to;
next_s.next_i = next_i;
next_s.power = s.power;
next_s.dist = next_s.now.euclid(next_s.next);
//真縦移動または真横移動したStateは特別扱い(保護)してもらう
next_s.dy = (int)delta.y;
next_s.dx = (int)delta.x;
update(mp1, next_s);
}
}
//最後の巻物に到達したらおしまい
if(arrived){
break;
}
//次のターンに進む
//枝刈りを行う
//{目的地,pointsにおけるidx} -> その目的地を目指すに当たって一番近い距離
//pointsにおけるidxは, 同じ目的地でも2回通る場合などが有りそれらを区別するため
std::map<pair<Pos,int>, float> ruiseki_min_dist;
//pointsにおけるidxが最大でどこまで進んでいるか
//idxが2つ以上先に進んでいるかつ同等以上に良い地形に居るような状態が存在する状態は,
//枝刈りをしqに追加しない
int ruiseki_max_next_i = -1;
//4種類のkind(terrain)について
rep(k, 4){
//mp1: 状態の現在の地形からmp2に飛ばす
//mp2: (次の目的地, 真縦移動または真横移動を行ったかどうか)から最良状態に飛ばす
const auto& mp2 = mp1[k];
for(auto pa2 : mp2){
chmax(ruiseki_max_next_i, pa2.second.next_i);
}
for(auto pa2 : mp2){
//idxが2つ以上先に進んでいるかつ同等以上に良い地形に居るような状態が存在するなら飛ばす
if(pa2.second.next_i <= ruiseki_max_next_i - 2) continue;
const Pos& next_p = pa2.second.next;
//より良い地形かつ目的地が一緒かつ目的地までの距離がより小さい状態が存在するなら飛ばす
if(ruiseki_min_dist.count({next_p,pa2.second.next_i}) > 0 && ruiseki_min_dist[{next_p,pa2.second.next_i}] < pa2.second.dist){
continue;
}
q.push(pa2.second);
ruiseki_min_dist[{next_p,pa2.second.next_i}] = pa2.second.dist;
}
}
}
//logsの最後が最終状態
//復元
int li = logs.size() - 1;
while(li != -1){
plan.push_back(logs[li].now);
li = logs[li].before_li;
}
plan.pop_back();
//逆順に復元したのでひっくり返す
reverse(all(plan));
return;
}
//------------------------------------------------------------------------------
/// 各ステージ開始時に呼び出される処理
/// @detail 各ステージに対する初期化処理が必要ならここに書きます
/// @param aStage 現在のステージ
void Answer::initialize(const Stage& aStage)
{
plan_idx = 0;
//input
kind_map.resize(N*N);
rep(y,N){
rep(x,N){
kind_map[y*N+x] = terrainToKind(aStage.terrain(Vector2(x+0.5f,y+0.5f)));
}
}
M.clear();
{
const auto& scrolls = aStage.scrolls();
m = scrolls.count();
M.resize(m);
rep(i,M.size()){
M[i] = {scrolls[i].pos().y, scrolls[i].pos().x};
}
}
S = {aStage.rabbit().pos().y, aStage.rabbit().pos().x};
M.push_back(S);
//主にワーシャルフロイドを行う
init_graph();
//bitDP
//訪問済みの巻物が1となるbit * (m+1) * MAKIMONO_V_NUM + 最後に訪問した巻物
//MAKIMONO_V_NUMが4または5の場合は, 各巻物について複数通りの頂点を考える
//i番目の巻物のj番目の頂点を最後に訪問した場合のidxは
//bit * (m+1) * MAKIMONO_V_NUM + i * MAKIMONO_V_NUM + j となる
vector<double> dp((1ll<<m) * (m+1) * MAKIMONO_V_NUM, LINF);
//mすなわちスタート地点を最後に訪問した状態
dp[m*MAKIMONO_V_NUM] = 0;
//復元用
vector<Pii> back((1ll<<m) * (m+1) * MAKIMONO_V_NUM, {-1,-1});
//ワーシャルフロイドで求めたdist_matrixは巻物以外の点が含まれていて扱いが面倒なので,
//巻物と初期地点のみで構成される配列に直す
vector<double> dist_matrix_without_kado;
dist_matrix_without_kado = vector<double>((m+1)*(m+1)*MAKIMONO_V_NUM*MAKIMONO_V_NUM);
rep(i,(m+1)*MAKIMONO_V_NUM){
rep(j,(m+1)*MAKIMONO_V_NUM){
dist_matrix_without_kado[i*(m+1)*MAKIMONO_V_NUM+j] = dist_matrix[i+kadoNum][j+kadoNum];
}
}
vector<int> bit_list;
rep(bit, (1<<m) - 1){
//bitを訪問済みで, jにいる状態から, iに移動
float power = 1;
rep(i,m){
power *= ((bit & (1<<i)) > 0 ? 1.1 : 1);
}
//bitの何桁目が1になっているか
bit_list.clear();
bit_list.reserve(m);
rep(i,m){
if((bit & (1<<i)) > 1) continue;
bit_list.push_back(i);
}
rep(_j, (m+1) * MAKIMONO_V_NUM){
int j = _j;
//full_bitdpフラグがfalseの場合は高速化を行う
//巻物jに対応するMAKIMONO_V_NUM個の頂点で移動を終えているもののうち,
//それまでの距離が最も小さいもののみを起点として更新を行う
if(!full_bitdp){
double min_val = INF;
rep(dj, MAKIMONO_V_NUM){
double val = dp[bit * (m+1) * MAKIMONO_V_NUM + _j+ dj];
if(val < min_val){
min_val = val;
j = _j + dj;
}
}
_j += MAKIMONO_V_NUM - 1;
}
//bitDPの更新
const double before_val = dp[bit * (m+1) * MAKIMONO_V_NUM + j];
if(before_val == (double)LINF) continue;
//_i: bitの0に対応するものそれぞれについて.
for(int _i : bit_list){
if(_i==j/MAKIMONO_V_NUM) continue;
//_i番目の巻物に対応する各頂点iについて, 移動先として検討する
for(int i = _i * MAKIMONO_V_NUM; i < _i * MAKIMONO_V_NUM + MAKIMONO_V_NUM; i++){
const double after_val = before_val + dist_matrix_without_kado[i*(m+1)*MAKIMONO_V_NUM+j] / power;
assert(after_val >= 0);
const int idx = (bit | (1<<_i)) * (m+1) * MAKIMONO_V_NUM + i;
if(dp[idx] > after_val){
dp[idx] = after_val;
back[idx] = {bit, j};
}
}
}
}
}
//復元
answer.clear();
int now_bit = (1<<m) - 1;
int now_j = -1;
float best_eval = LINF;
//最適な経路の終着点を探す
rep(j,m * MAKIMONO_V_NUM){
if(best_eval > dp[now_bit * (m+1) * MAKIMONO_V_NUM + j]){
best_eval = dp[now_bit * (m+1) * MAKIMONO_V_NUM + j];
now_j = j;
}
}
//逆順にたどって復元
while(now_j != m * MAKIMONO_V_NUM){
answer.push_back(now_j);
Pii& next = back[now_bit * (m+1) * MAKIMONO_V_NUM + now_j];
now_bit = next.first;
now_j = next.second;
}
//逆順なのでひっくり返す
reverse(all(answer));
//辿るべき頂点がanswerに入ってるので
//それをもとに辿るべきPosを求める
planning();
}
//------------------------------------------------------------------------------
/// 毎フレーム呼び出される処理
/// @detail 移動先を決定して返します
/// @param aStage 現在のステージ
/// @return 移動の目標座標
Vector2 Answer::getTargetPos(const Stage& aStage)
{
assert(plan_idx < plan.size());
const Pos& p = plan[plan_idx++];
return Vector2(p.x, p.y);
}
//------------------------------------------------------------------------------
/// 各ステージ終了時に呼び出される処理
/// @detail 各ステージに対する終了処理が必要ならここに書きます
/// @param aStage 現在のステージ
void Answer::finalize(const Stage& aStage)
{
#if LOCAL
cerr<<g<<":"<<aStage.turn()<<endl;
#endif
g++;
}
} // namespace
// EOF