codevs_5_latest.cpp

/*
オプション：
Dを付与して実行するとログをオエーする
example :: codevs D < stdin.txt 2> out.log
Rを付与して実行するとパラメータにランダム要素が加わる
Tを付与して実行すると攻撃、防衛しない。
Uを付与して実行すると攻撃しない。
T,Uは重複できない。

コンパイラ：
VS2013 x64 (cl /EHsc /O2 codevs.cpp)
cygwinのg++4.9.3でもコンパイルは通るように 実行は未検証

危険な可読性：
Entityクラスの異常な汎用性
Entity.idメンバに距離突っ込んだりしてる。
推奨されるconst表記が無い。
goto使用。
コメントが無い。
統一しない書き方。
間違った英語
その他

開発メモ：
壁端検出は不要(Wの検出でおｋ)
昇順にするために、マイナスにする
seed:1 -> quick:cost1
seed:123 -> quick+round
79850
seed:41348 -> enemydril:cost1
seed:529081492790143254 -> quick:cost2
seed:6892501092310159412 -> maze
seed:31416 -> maze(round) なやみ
seed789 -> 上の方にsoulかたまってる
seed387 -> dup3 edup2 estone3 drill3 edrill1 hiretu連敗

361 -> old/codevs20160314_150109に5連敗

毎回predictDogやってるような気はするので
速度が気になるようならNinjaActionに持たせる？

メモリの問題が露呈

checkerは走査の跡であって、候補の跡ではない

回転切りしない（する前に分身・超高速が発動する）。
->消費Ｓも大きいので発動タイミングについて考察

岩を避けるＡＩを削除

分身発動・ninja1が確定した後、
ninja2が岩を移動させ犬の移動経路が変更・ninja1が死ぬ事故

道中の評価関数を含める
UR!=RUである（壁際など）

4000->5000
limit 2->3

分身使ってソウル拾えるならば使う
*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cstdio>
#include <cmath>
#include <sstream>
#include <stdexcept>
#include <random>
#include <list>
//#include <map>

using namespace std;

#define oserr (debugmode?cerr:nullout)

struct null_streambuf:streambuf {
    int overflow(int c){return c;}
}nullbuff;

bool debugmode;
bool randommode = false;
int trustmode;

#ifdef __GNUC__ // gcc対策
ostream nullout(&nullbuff);
#else
ostream& nullout = ostream(&nullbuff);
#endif

inline void debugchk(){
	static int c = 0;
	oserr << "dbg:chkpoint - " << (c++) << endl;
}

random_device drnd;
inline int rand(int d,int l,int h){
	return !randommode ? d : (drnd() % (h - l + 1) + l);
}

inline int n1dist(int x1, int y1, int x2, int y2){
	return abs(x1 - x2) + abs(y1 - y2);
}

inline int stepfunc(int x){
	return x > 0 ? x : 0;
}

inline int limit(int x, int l, int h){
	return x < l ? l : (h < x ? h : x);
}



// 万能構造体
class Entity{
public: // がばがば
    int id;
    int x,y;
	void *link; // 追加,データ引っさげたい用
	//Entity(Entity& e) :id(e.id), x(e.x), y(e.y){}
	Entity(int id, int x, int y,void *link) :id(id), x(x), y(y),link(link){}
	Entity(int id, int x, int y) :id(id), x(x), y(y){}
	//Entity(Entity& e,void *link) :id(e.id), x(e.x), y(e.y),link(link){}
    Entity(int x,int y):id(0),x(x),y(y){}
    Entity():id(0),x(-1),y(-1){}

    bool operator <(const Entity& e) const{
        return id<e.id;
    }
    string tostring(){
        ostringstream os;
        os << "E:"<<id<<" ["<<x<<","<<y<<"]"<<flush;
        return os.str();
    }
	void set(Entity &e){
		x = e.x;
		y = e.y;
		link = e.link;
		id = e.id;
	}

};

// 万能二次元配列
class Field{
private:
    int psix=0,psiy=0;
public:
    int width,height;
    vector<vector<int>> data;

    Field():width(0),height(0){}

    Field(int w,int h):width(w),height(h){
        data.assign(w,vector<int>(h,0));
    };

	void resize(int w,int h){
		width = w;
		height = h;
		data.assign(w, vector<int>(h, 0));
	}

    vector<int>& operator[](int idx){
        return data[idx];
    }
    void push(int d){
        (*this)[psix][psiy]=d;
        if (width<=++psix){
            psix=0;
            if (height<=++psiy)
                psiy=0;
        }
    }
    void fill(int d){
        for (vector<int> &v:data)
            for (int &e:v)
                e=d;
    }

	void setEntity(vector<Entity> &ve){
		//fill(0);
		for (Entity &e : ve)
			data[e.x][e.y] = 1;
	}

    Field& operator+=(Field& f){
        if (f.width!=width || f.height!=height)
			throw invalid_argument("class[Field] operator[+=] exception.");

        for (int y=0;y<height;y++)
            for (int x=0;x<width;x++)
                data[x][y]+=f[x][y];

        return *this;
    }

    Field& operator-=(Field& f){
        if (f.width!=width || f.height!=height)
			throw invalid_argument("class[Field] operator[-=] exception.");

        for (int y=0;y<height;y++)
            for (int x=0;x<width;x++)
                data[x][y]-=f[x][y];

        return *this;
	}
	int roundsum12(int x, int y){
		return data[x - 1][y - 1]
			+ data[x - 1][y]
			+ data[x - 1][y + 1]
			+ data[x][y + 1]
			+ data[x + 1][y + 1]
			+ data[x + 1][y]
			+ data[x + 1][y - 1]
			+ data[x][y - 1]
			+ ((y < height - 2) ? data[x][y + 2] : 0)
			+ ((x < width - 2) ? data[x + 2][y] : 0)
			+ ((y > 1) ? data[x][y - 2] : 0)
			+ ((x > 1) ? data[x - 2][y] : 0);
	}
	int roundsum(int x, int y,int c){ 
		return (data[x - 1][y - 1]==c)  
			+ (data[x - 1][y]==c)		  
			+ (data[x - 1][y + 1]==c)	  
			+ (data[x][y + 1] == c)	  
			+ (data[x + 1][y + 1] == c) 
			+ (data[x + 1][y] == c)	  
			+ (data[x + 1][y - 1] == c) 
			+ (data[x][y - 1] == c);
	}
	int roundsum(int x,int y){
		return data[x - 1][y - 1]
			+ data[x - 1][y]
			+ data[x - 1][y + 1]
			+ data[x][y + 1]
			+ data[x + 1][y + 1]
			+ data[x + 1][y]
			+ data[x + 1][y - 1]
			+ data[x][y - 1];
	}
	int roundsum4(int x, int y,int c){
		return (data[x - 1][y] == c)
			+ (data[x][y + 1] == c)
			+ (data[x + 1][y] == c)
			+ (data[x][y - 1] == c);
	}
	int roundsum4(int x, int y){
		return data[x - 1][y]
			+ data[x][y + 1]
			+ data[x + 1][y]
			+ data[x][y - 1];
	}

    void eprintchar(){
        /*
        for (vector<int>& e:data){
            for (int& c:e){
                oserr<<(char)c;
            }
            oserr<<endl;
        } */
        for (int y=0;y<height;y++){
            for (int x=0;x<width;x++)
                oserr<<(char)data[x][y];
            oserr<<endl;
        }
    }

    void eprintint(){
        char str[64];
        for (int y=0;y<height;y++){
            for (int x=0;x<width;x++){
                sprintf(str,"%4d",data[x][y]);
                oserr<<str;
            }
            oserr<<endl;
        }
    }

};

class PlayerStatusCompact{


};

class PlayerStatus{
public:
    int spell;
    Field field;
    int nninja; // contantly
    int ndog;
    int nsoul;
	int nableSoul;
    vector<Entity> ninja;
    vector<Entity> dog;
    vector<Entity> soul;
	vector<Entity> ableSoul;
    //vector<int> usedSpell;
	// for stonespell
	stack<Entity> stoneSpell;

    void setFieldSize(int w,int h){
        field=Field(w,h);
    }
    void reset(){
        ninja.clear();
        dog.clear();
        soul.clear();
		//usedSpell.clear();
    }
	bool isDogHere(int x,int y){
		for (Entity &e : dog)
			if (e.x == x&&e.y == y)
				return true;
		return false;
	}
	bool isSoulHere(int x, int y){
		for (Entity &e : soul)
			if (e.x == x&&e.y == y)
				return true;
		return false;
	}
	void calcScore(Field &,bool,bool);
	void calcScore(Field &sf,bool update){
		calcScore(sf,update, true);
	}

	// TODO:Field統合(setEntity)
	void setDogMap(Field &out){
		out.fill(0);
		for (Entity &e : dog)
			out[e.x][e.y] = 1;
	}
	void setSoulMap(Field &out){
		out.fill(0);
		for (Entity &e : soul)
			out[e.x][e.y] = 1;
	}
	// 落石等のスペル詠唱用
	void fieldOverride(int c, int x, int y){
		Entity e(field[x][y], x, y);
		stoneSpell.push(e);
		field[x][y] = c;

		calcAbleSoul(); // ablesoul再計算
	}
	void fieldUndo(){
		if (stoneSpell.empty()) return;
		Entity &e = stoneSpell.top();
		field[e.x][e.y] = e.id;
		stoneSpell.pop();

		calcAbleSoul(); // ablesoul再計算
	}

	// 0:not able 1:moveable 2:pushable -1 error
	// p_field:代わりにこのp_fieldを走査対象とする@任意
	int isNinjaMoveable(int x, int y, int vx, int vy,Field &p_field){
		if (2 <= vx*vx + vy*vy)
			throw invalid_argument("class[Field] isNinjaMoveable exception.");
		// vx[-1,0,1] vy[-1,0,1]
		int &i = p_field[x + vx][y + vy];
		if (i == '_') return 1;
		if (i == 'W') return 0;
		if (i == 'O'){
			int nx = x + vx * 2, ny = y + vy * 2;
			if (p_field[nx][ny] != '_') return 0;
			for (Entity &e : dog)
				if (e.x == nx && e.y == ny) return 0;
			for (Entity &e : ninja)
				if (e.x == nx && e.y == ny) return 0;
			return 2;
		}
		return 0;
	}
	int isNinjaMoveable(int x, int y, int vx, int vy){
		return isNinjaMoveable(x, y, vx, vy, field);
	}

	void attack(int ninjaid){
		Entity &nj = ninja[ninjaid];
		vector<Entity> qdog = dog;
		dog.clear(); ndog = 0;
		for (Entity &e : qdog){
			if ((e.x - nj.x)*(e.x - nj.x) > 1 ||
				(e.y - nj.y)*(e.y - nj.y) > 1){
				ndog++;
				dog.push_back(Entity(e));
			}
		}
	}

	// x,y=>ninjaPos. vx,vy=>ninjaVel
	bool pushRock(int x, int y, int vx, int vy, Field &p_field){
		if (2 <= vx*vx + vy*vy)
			throw invalid_argument("class[Field] pushRock exception.");
		if (isNinjaMoveable(x, y, vx, vy) != 2) return false;
		p_field[x + vx][y + vy] = '_';
		p_field[x + vx * 2][y + vy * 2] = 'O';
		if (&p_field == &field) calcAbleSoul(); // ablesoul再計算
		return true;
	}
	bool pushRock(int x, int y, int vx, int vy){
		return pushRock(x, y, vx, vy, field);
	}
	void calcAbleSoul(){
		ableSoul.clear();
		nableSoul = 0;
		for (Entity &e : soul){
			if (field[e.x][e.y] == '_' || (
				(field[e.x - 1][e.y] == '_' && isNinjaMoveable(e.x - 1, e.y,  1, 0)) ||
				(field[e.x + 1][e.y] == '_' && isNinjaMoveable(e.x + 1, e.y, -1, 0)) ||
				(field[e.x][e.y - 1] == '_' && isNinjaMoveable(e.x, e.y - 1, 0,  1)) ||
				(field[e.x][e.y + 1] == '_' && isNinjaMoveable(e.x, e.y + 1, 0, -1)))){
				nableSoul++;
				ableSoul.push_back(e);
			}
		}
	}
};

class Game{
public:
    int time;
    int nspell;
    vector<int> spellcost;
    PlayerStatus me;
	PlayerStatus enemy;
	Field scorefieldMe;
	Field scorefieldEnemy;
    void reset(){
        spellcost.clear();
        me.reset();
        enemy.reset();
    }
};

class NinjaAction{
public:
	int x, y;
	int sx, sy;
	int vx = 0, vy = 0;
	queue<int> history;
	int historysize = 0;
	int score=0;
	int lastscore=0;
	int csscore = 0;

	NinjaAction(int x, int y) :x(x), y(y), sx(x), sy(y), score(0), lastscore(0){}
	NinjaAction() :x(0), y(0), sx(0), sy(0), score(0), lastscore(0){}
	NinjaAction(const NinjaAction &na){
		sx = na.sx; sy = na.sy;
		vx = na.vx; vy = na.vy;
		x = na.x; y = na.y;
		history = queue<int>(na.history);
		historysize = na.historysize;
		score = na.score;
		lastscore = na.lastscore;
	}

	void historyclear(){
		while (!history.empty())
			history.pop();
		historysize = 0;
	}
	void sets(int _x, int _y){ sx = _x; sy = _y; x = _x; y = _y; vx = 0; vy = 0; historyclear(); }
	NinjaAction& moveLeft(){
		x--; vx--;
		history.push('L');
		if (historysize++){
			csscore = history.front() != 'L';
		}
		return *this;
	}
	NinjaAction& moveRight(){
		x++; vx++;
		history.push('R');
		if (historysize++){
			csscore = history.front() != 'R';
		}
		return *this;
	}
	NinjaAction& moveUp(){
		y--; vy--;
		history.push('U');
		if (historysize++){
			csscore = history.front() != 'U';
		}
		return *this;
	}
	NinjaAction& moveDown(){
		y++; vy++;
		history.push('D');
		if (historysize++){
			csscore = history.front() != 'D';
		}
		return *this;
	}
	int distance() const{
		return abs(x - sx) + abs(y - sy);
	}
	int cmdsize() const{
		return historysize;
	}
	bool operator <(const NinjaAction& e) const{

		return score < e.score;
	}
	bool equals(const NinjaAction& e){
		if (e.sx != sx || e.sy != sy)return false;
		return history == e.history;
	}
	Entity toEntity(int id){
		return Entity(id, x, y);
	}
	Entity toEntity(){
		return toEntity(0);
	}

	int act(PlayerStatus &ps,Entity *to){
		int c;
		int nx = sx, ny = sy;
		bool push = false; // TODO:
		bool fail = false; // TODO:
		int soul = 0; // 

		history.push('$');
		while ((c = history.front()) != '$'){
			history.pop();
			history.push(c);
			switch (c){
			case 'U':
				if (ps.isNinjaMoveable(nx, ny, 0, -1) <= 0){
					fail = true; continue;
				}
				ps.pushRock(nx, ny, 0, -1);
				ny--;
				break;
			case 'L':
				if (ps.isNinjaMoveable(nx, ny, -1, 0) <= 0){
					fail = true; continue;
				}
				ps.pushRock(nx, ny, -1, 0);
				nx--;
				break;
			case 'R':
				if (ps.isNinjaMoveable(nx, ny, 1, 0) <= 0){
					fail = true; continue;
				}
				ps.pushRock(nx, ny, 1, 0);
				nx++;
				break;
			case 'D':
				if (ps.isNinjaMoveable(nx, ny, 0, 1) <= 0){
					fail = true; continue;
				}
				ps.pushRock(nx, ny, 0, 1);
				ny++;
				break;
			}
			// soul消化
			for (auto it = ps.soul.begin(); it != ps.soul.end();it++){
				if ((*it).x == nx && (*it).y == ny){
					soul++;
					ps.soul.erase(it);
					break;
				}
			}
		}
		history.pop();
		ps.calcAbleSoul();

		if (to != nullptr){
			to->x = nx;
			to->y = ny;
		}
		
		return ((int)fail) | ((int)push << 1) | ((soul&7) << 2);
	}
	int act(PlayerStatus &ps){
		return act(ps, nullptr);
	}

	// 返り値に岩を押した回数を「無理やり」追加
	// TODO:actと統合したいかも
	int test(PlayerStatus &ps, Entity ninja, int &outSoul, int &outFail, int &outRisk){
		int c;
		int nx, ny;
		Field dfield = ps.field;
		Field dogmap(ps.field.width, ps.field.height);
		ps.setDogMap(dogmap);
		Field entitymap(ps.field.width, ps.field.height);
		entitymap.setEntity(ps.dog);
		entitymap.setEntity(ps.ninja);
		Field safemap = entitymap; // 岩は落とせない
		entitymap.setEntity(ps.soul);
		Field soulmap(ps.field.width, ps.field.height);
		soulmap.setEntity(ps.soul);
		nx = ninja.x;
		ny = ninja.y;
		int nrock=0;
		bool first = true;

		outSoul = 0; outFail = 0;
		outRisk = 0;

		bool firstRisk=false; // tekitou

		history.push('$');
		while ((c = history.front()) != '$'){
			history.pop();
			history.push(c);
			switch (c){
			case 'U':
				if (ps.isNinjaMoveable(nx, ny, 0, -1,dfield) == 0){
					outFail++; continue;
				}
				if (ps.pushRock(nx, ny, 0, -1, dfield)){
					nrock++;
					if (dogmap.roundsum4(nx, ny)) outRisk++;
				}

				if (dogmap.roundsum4(nx, ny)){
					if (1 < ny && dfield[nx][ny - 2] != '_')
						outRisk++;
					if (entitymap[nx][ny - 2] && !safemap[nx][ny - 1])outRisk++;
				}
				if (firstRisk){
					firstRisk = false;
					if (ps.isNinjaMoveable(ninja.x, ninja.y, 0, -1, dfield) &&
						dogmap.roundsum4(ninja.x, ninja.y - 1))
						outRisk++;
				}
				ny--;
				break;
			case 'L':
				if (ps.isNinjaMoveable(nx, ny, -1, 0, dfield) == 0){
					outFail++; continue;
				}
				if (ps.pushRock(nx, ny, -1, 0, dfield)){
					nrock++;
					if (dogmap.roundsum4(nx, ny)) outRisk++;
				}

				if (dogmap.roundsum4(nx, ny)){
					if (1 < ny && dfield[nx - 2][ny] != '_')
						outRisk++;
					if (entitymap[nx - 2][ny] && !safemap[nx - 1][ny])outRisk++;
				}

				if (firstRisk){
					firstRisk = false;
					if (ps.isNinjaMoveable(ninja.x, ninja.y, -1, 0, dfield) &&
						dogmap.roundsum4(ninja.x - 1, ninja.y))
						outRisk++;
				}
				nx--;
				break;
			case 'R':
				if (ps.isNinjaMoveable(nx, ny, 1, 0, dfield) == 0){
					outFail++; continue;
				}
				if (ps.pushRock(nx, ny, 1, 0, dfield)){
					nrock++;
					if (dogmap.roundsum4(nx, ny)) outRisk++;
				}

				if (dogmap.roundsum4(nx, ny)){
					if (1 < ny && dfield[nx + 2][ny] != '_')
						outRisk++;
					if (entitymap[nx + 2][ny] && !safemap[nx + 1][ny])outRisk++;
				}
				if (firstRisk){
					firstRisk = false;
					if (ps.isNinjaMoveable(ninja.x, ninja.y, 1, 0, dfield) &&
						dogmap.roundsum4(ninja.x + 1, ninja.y))
						outRisk++;
				}
				nx++;
				break;
			case 'D':
				if (ps.isNinjaMoveable(nx, ny, 0, 1, dfield) == 0){
					outFail++; continue;
				}
				if (ps.pushRock(nx, ny, 0, 1, dfield)){
					nrock++;
					if (dogmap.roundsum4(nx, ny)) outRisk++;
				}
				if (dogmap.roundsum4(nx, ny)){
					if (1 < ny && dfield[nx][ny + 2] != '_')
						outRisk++;
					if (entitymap[nx][ny + 2] && !safemap[nx][ny + 1])outRisk++;
				}
				if (firstRisk){
					firstRisk = false;
					if (ps.isNinjaMoveable(ninja.x, ninja.y, 0, 1, dfield) &&
						dogmap.roundsum4(ninja.x, ninja.y + 1))
						outRisk++;
				}
				ny++;
				break;
			}
			if (soulmap[nx][ny]){
				soulmap[nx][ny] = 0;
				outSoul++;
			}
			if (first && outRisk) firstRisk = true;
			first = false;
		}
		history.pop();
		return nrock;
	}
	int test(PlayerStatus &ps, Entity &ninja, int &outSoul, int &outFail){
		int dammy;
		return test(ps, ninja, outSoul, outFail, dammy);
	}
	// 岩を押したとき、最初に押した岩の座標を得る
	// 押してない->id=0
	Entity testRockPos(PlayerStatus &ps, int ninjaID){
		int c;
		int nx, ny;
		Field dfield = ps.field;
		nx = ps.ninja[ninjaID].x;
		ny = ps.ninja[ninjaID].y;
		Entity rrock(0, 0, 0);
	
		history.push('$');
		while ((c = history.front()) != '$'){
			history.pop();
			history.push(c);
			switch (c){
			case 'U':
				if (ps.isNinjaMoveable(nx, ny, 0, -1, dfield) == 0){
					continue;
				}
				if (rrock.id == 0 && ps.pushRock(nx, ny, 0, -1, dfield)){
					rrock.id = 1;
					rrock.x = nx;
					rrock.y = ny - 1;
				}
				ny--;
				break;
			case 'L':
				if (ps.isNinjaMoveable(nx, ny, -1, 0, dfield) == 0){
					continue;
				}
				if (rrock.id == 0 && ps.pushRock(nx, ny, -1, 0, dfield)){
					rrock.id = 1;
					rrock.x = nx - 1;
					rrock.y = ny;
				}
				nx--;
				break;
			case 'R':
				if (ps.isNinjaMoveable(nx, ny, 1, 0, dfield) == 0){
					continue;
				}
				if (rrock.id == 0 && ps.pushRock(nx, ny, 1, 0, dfield)){
					rrock.id = 1;
					rrock.x = nx + 1;
					rrock.y = ny;
				}
				nx++;
				break;
			case 'D':
				if (ps.isNinjaMoveable(nx, ny, 0, 1, dfield) == 0){
					continue;
				}
				if (rrock.id == 0 && ps.pushRock(nx, ny, 0, 1, dfield)){
					rrock.id = 1;
					rrock.x = nx;
					rrock.y = ny + 1;
				}
				ny++;
				break;
			}
		}
		history.pop();
		return rrock;
	}
};

ostream& operator <<(ostream& os, NinjaAction &na){
	int c;
	na.history.push('$');
	while ((c = na.history.front()) != '$'){
		na.history.pop();
		if (0<c)
			os << (char)c;
		na.history.push(c);
	}
	na.history.pop();
	return os;
}

Game game;
Field rectScore; // はしっこ定数
Field ninjaShadow;
int gameLoopCnt = 0;
//History spellHistory;

int consoleLoad(){
    char c;
    int i,j,n,w,h;
    cin>>game.time;
    //if (!(cin >> game.time))
    //    return 1;
    cin>>n;
    game.nspell=n;
    for (i=0;i<n;i++){
        cin>>j;
        game.spellcost.push_back(j);
	}

    // Me
    cin>>game.me.spell;
    cin>>h>>w;
    game.me.setFieldSize(w,h);
    for (i=0;i<w*h;i++){
        cin >> c;
        if (c!='W'&&c!='_'&&c!='O'){
            i--;continue;
        }
        game.me.field.push((int)c);
    }
    cin>>n;game.me.nninja=n;
    for (i=0;i<n;i++){
        cin>>j>>h>>w;
        game.me.ninja.push_back(Entity(j,w,h));
	}
    cin>>n;game.me.ndog=n;
    for (i=0;i<n;i++){
        cin>>j>>h>>w;
        game.me.dog.push_back(Entity(j,w,h));
    }
    cin>>n;game.me.nsoul=n;
    for (i=0;i<n;i++){
        cin>>h>>w;
        game.me.soul.push_back(Entity(w,h));
	}
    n=game.nspell;
    for (i=0;i<n;i++){
        cin>>j;
        //game.me.usedSpell.push_back(j);
	}
    // Enemy
    cin>>game.enemy.spell;
    cin>>h>>w;
    game.enemy.setFieldSize(w,h);
    for (i=0;i<w*h;i++){
        cin >> c;
        if (c!='W'&&c!='_'&&c!='O'){
            i--;continue;
        }
        game.enemy.field.push((int)c);
    }
    cin>>n;game.enemy.nninja=n;
    for (i=0;i<n;i++){
        cin>>j>>h>>w;
        game.enemy.ninja.push_back(Entity(j,w,h));
    }
    cin>>n;game.enemy.ndog=n;
    for (i=0;i<n;i++){
        cin>>j>>h>>w;
        game.enemy.dog.push_back(Entity(j,w,h));
    }
    cin>>n;game.enemy.nsoul=n;
    for (i=0;i<n;i++){
        cin>>h>>w;
        game.enemy.soul.push_back(Entity(w,h));
    }
    n=game.nspell;
    for (i=0;i<n;i++){
        cin>>j;
        //game.enemy.usedSpell.push_back(j);
    }

	// calculate
	game.me.calcAbleSoul();
	game.enemy.calcAbleSoul();

	// ninjaShadow initialize
	if (ninjaShadow.width == 0){
		ninjaShadow = Field(game.me.field.width, game.me.field.height);
	}
	if (rectScore.width == 0){
		//int &w = game.me.field.width, &h = game.me.field.height;
		//int n = ((w < h ? w : h) - 2) / 2;
		//rectScore = Field(w,h);
		//for (i = n; 1 <= i; i--)
		//	for (j = i; 1 <= j; j--){
		//		rectScore[j][i - j + 1]             = (n - i + 1) * 3/2; // 6*4
		//		rectScore[w - j - 1][i - j + 1]     = (n - i + 1) * 3/2;
		//		rectScore[j][h - i + j - 2]         = (n - i + 1) * 3/2;
		//		rectScore[w - j - 1][h - i + j - 2] = (n - i + 1) * 3/2;
		//	}

		int &w = game.me.field.width, &h = game.me.field.height;
		rectScore = Field(w, h);
		rectScore.fill(0);
		for (i = 1; i < w - 1; i++){
			rectScore[i][1] = 8;
			rectScore[i][h-2] = 8;
		}
		for (i = 1; i < h - 1; i++){
			rectScore[1][i] = 8;
			rectScore[w-2][i] = 8;
		}
		rectScore[1][1] = 40;
		rectScore[w-2][1] = 40;
		rectScore[1][h-2] = 40;
		rectScore[w-2][h-2] = 40;
	}

    return 0;
}


Field createDistanceField(vector<Entity> &ve, Field &field){
	Field distField(field.width, field.height);
	queue<Entity> eq;
	for (Entity &e : ve)
		eq.push(Entity(0, e.x, e.y));

	distField.fill(999);
	for (; !eq.empty(); eq.pop()){
		Entity &e = eq.front();
		int &dist = distField[e.x][e.y];
		if (field[e.x][e.y] != '_') continue;
		if (dist <= e.id) continue;
		dist = e.id;
		e.id++;
		eq.push(Entity(e.id, e.x - 1, e.y));
		eq.push(Entity(e.id, e.x + 1, e.y));
		eq.push(Entity(e.id, e.x, e.y - 1));
		eq.push(Entity(e.id, e.x, e.y + 1));
	}
	return distField;
}
//_____________________________________
//calc...
//


void predictDog(PlayerStatus &ps, vector<Entity> &target){

	if (ps.dog.size() <= 0) return;

	Field distField = createDistanceField(target, ps.field);

	vector<Entity> dogs;

	sort(ps.dog.begin(), ps.dog.end()); // ID昇順


	for (Entity &e : ps.dog){
		dogs.push_back(Entity(
			distField[e.x][e.y],e.x,e.y,&e));
	}
	stable_sort(dogs.begin(), dogs.end()); // 距離順

	for (Entity &e : dogs){
		if (e.id - 1 == distField[e.x][e.y-1]){
			bool flg = false;
			for (Entity &f: ps.dog)
				if (f.x == e.x && f.y == e.y - 1){ flg = true; break; }
			if (!flg){
				((Entity*)(e.link))->y -= 1; // proceed;
				continue;
			}
		}
		if (e.id - 1 == distField[e.x - 1][e.y]){
			bool flg = false;
			for (Entity &f : ps.dog)
				if (f.x == e.x - 1 && f.y == e.y){ flg = true; break; }
			if (!flg){
				((Entity*)(e.link))->x -= 1; // proceed;
				continue;
			}
		}
		if (e.id - 1 == distField[e.x + 1][e.y]){
			bool flg = false;
			for (Entity &f : ps.dog)
				if (f.x == e.x + 1 && f.y == e.y){ flg = true; break; }
			if (!flg){
				((Entity*)(e.link))->x += 1; // proceed;
				continue;
			}
		}
		if (e.id - 1 == distField[e.x][e.y + 1]){
			bool flg = false;
			for (Entity &f : ps.dog)
				if (f.x == e.x && f.y == e.y + 1){ flg = true; break; }
			if (!flg){
				((Entity*)(e.link))->y += 1; // proceed;
				continue;
			}
		}
	}

	return ;
}
void predictDog(PlayerStatus &ps){
	predictDog(ps, ps.ninja);
}

#ifdef __GNUC__ // gcc対策
void predictDog(PlayerStatus &ps, Entity e){
	vector<Entity> ve(1, e);
	predictDog(ps, ve);
}
#else
void predictDog(PlayerStatus &ps, Entity &e){
	predictDog(ps, vector<Entity>(1, e));
}
#endif

void PlayerStatus::calcScore(Field &scorefield,bool update,bool penalty){
    int x,y;
    Field fsct(field.width,field.height);
	Field dogMap(field.width, field.height);
	queue<Entity> stl;

	if (scorefield.width == 0){
		scorefield.resize(field.width, field.height);
	}

	scorefield.fill(0);

	setDogMap(dogMap);

	if (update){
		// ninjaShadow calc
		// 同じ場所にとどまらない工夫
		for (Entity e : ninja){
			ninjaShadow[e.x][e.y] += 7 + rand(0, -2, 7);
			ninjaShadow[e.x - 1][e.y] += 2;
			ninjaShadow[e.x][e.y - 1] += 2;
			ninjaShadow[e.x + 1][e.y] += 2;
			ninjaShadow[e.x][e.y + 1] += 2;
		}
		for (y = 1; y < field.height - 1; y++)
			for (x = 1; x < field.width - 1; x++)
				ninjaShadow[x][y] -= (0 < ninjaShadow[x][y]) * 2;
	}
	if (penalty){
		scorefield -= ninjaShadow;
		scorefield -= rectScore; // すみっこ減点
	}



	if (penalty){
		// わんこ
		fsct.fill(0);
		for (Entity e : dog){
			stl.push(Entity(120 + rand(0, -20, 20), e.x, e.y));
		}
		for (; !stl.empty(); stl.pop()){
			Entity& e = stl.front();
			if (fsct[e.x][e.y] >= e.id) continue;
			if (field[e.x][e.y] != '_') continue;
			fsct[e.x][e.y] = e.id; e.id -= 45;
			if (e.id <= 0) continue;
			stl.push(Entity(e.id, e.x - 1, e.y));
			stl.push(Entity(e.id, e.x, e.y - 1));
			stl.push(Entity(e.id, e.x + 1, e.y));
			stl.push(Entity(e.id, e.x, e.y + 1));
		}
		scorefield -= fsct;
	}

    // ぴょんやん
	fsct.fill(0);
	for (Entity e : ableSoul){ // MEMO:ableSoulここだけ...
		stl.push(Entity(140 + rand(0, -20, 80), e.x, e.y));
    }
	for (; !stl.empty();stl.pop()){
        Entity& e=stl.front();
		if (fsct[e.x][e.y] >= e.id) continue;
		if (field[e.x][e.y] == 'W') continue;
		if (field[e.x][e.y] == 'O'){
			if (field.roundsum(e.x, e.y, '_') <= 4) continue; // 通行不能ペナルティ
			e.id -= 4; // 岩ペナルティ
		}
        fsct[e.x][e.y]=e.id;e.id-=3;
        if (e.id<=0) continue;
		stl.push(Entity(e.id, e.x - 1, e.y));
		stl.push(Entity(e.id, e.x, e.y - 1));
		stl.push(Entity(e.id, e.x + 1, e.y));
		stl.push(Entity(e.id, e.x, e.y + 1));
    }
    scorefield+=fsct;

	// MEMO:need penaltyFlg?
	// マップペナルティ
	fsct.fill(0);
	int c;
	for (y = 1; y < field.height-1; y++)
		for (x = 1; x < field.width-1; x++){
			c = 0;
			c += isNinjaMoveable(x, y, -1, 0) == -1 ? 1 : 0;
			c += isNinjaMoveable(x, y, 1, 0) == -1 ? 1 : 0;
			c += isNinjaMoveable(x, y, 0, -1) == -1 ? 1 : 0;
			c += isNinjaMoveable(x, y, 0, 1) == -1 ? 1 : 0;
			fsct[x][y] = 2*c*c;
		}
	scorefield -= fsct;

}

Entity calcTry2Attack(){
	int x, y;
	Entity result;
	Field checker(7, 7);
	queue<NinjaAction> qe;
	vector<NinjaAction>ae;
	vector<NinjaAction>be;
	vector<NinjaAction>rac;
	bool failempty;
	Field dogMap(game.enemy.field.width, game.enemy.field.height);
	//Field soulMap(game.enemy.field.width, game.enemy.field.height);
	game.enemy.setDogMap(dogMap);
	//game.enemy.setSoulMap(soulMap);

	Field wallMap(game.enemy.field.width, game.enemy.field.height);
	wallMap.fill(0);
	wallMap += dogMap;
	for (y = 0; y < game.enemy.field.height; y++)
		for (x = 0; x < game.enemy.field.width; x++)
			if (game.enemy.field[x][y] != '_')
				wallMap[x][y] |= 1;


	Entity perhaps(-1,0,0); // 曖昧な術を忍者id0で発動されても困る

	for (int idx = 0; idx < game.enemy.nninja; idx++){
		Entity &ninja = game.enemy.ninja[idx];
		checker.fill(0);
		ae.clear();
		be.clear();
		rac.clear();
		failempty = true;

		qe.push(NinjaAction(ninja.x, ninja.y));

		for (; !qe.empty(); qe.pop()){
			NinjaAction &na = qe.front();
			int soul, fail;
			na.score = na.test(game.enemy, ninja, soul, fail);
			if (0<fail) continue;
			if (checker[3 + na.vx][3 + na.vy]) continue;
			
			checker[3 + na.vx][3 + na.vy] = 1;
			ae.push_back(NinjaAction(na));
			if (2 <= na.cmdsize()){ continue; }
			qe.push(NinjaAction(na).moveDown());
			qe.push(NinjaAction(na).moveRight());
			qe.push(NinjaAction(na).moveLeft());
			qe.push(NinjaAction(na).moveUp());
		}
		for (NinjaAction &na : ae){
			int soul, fail, risk;
			PlayerStatus pspd = game.enemy;

			na.act(pspd);
			predictDog(pspd, na.toEntity());

			if (pspd.isDogHere(na.x, na.y)){
				failempty = false;
				continue;
			}
			na.test(game.enemy, ninja, soul, fail, risk);
			if (risk){
				rac.push_back(na);
			}

			be.push_back(na);
		}

		// 敵の動きを予測した敵分身
		if (be.empty()){
			// 相手はなすすべなし？スペル？
			// 相手の分身を予測して敵分身を仕掛ける
			// 最大でも12マスしか無いので全部列挙を試す
			if ((game.enemy.spell >= game.spellcost[5] || game.enemy.spell >= game.spellcost[0])
				&& game.me.spell >= game.spellcost[6] && !failempty){
				Entity best(0, 0, 0);
				int x, y, nx, ny, c;
				for (x = -2; x <= 2; x++){
					for (y = -2; y <= 2; y++){
						nx = ninja.x - x; ny = ninja.y;
						if (nx <= 0 || ny <= 0 || game.enemy.field.width - 1 <= nx || 
							game.enemy.field.height - 1 <= ny || 
							game.enemy.field[nx][ny]!='_') continue;
						PlayerStatus ps = game.enemy;
						predictDog(ps, Entity(0, nx, ny));
						c = 0;
						for (Entity &e : ps.dog){
							if (n1dist(ninja.x, ninja.y, e.x, e.y) <= 2)c++;
						}
						if (best.id < c){
							best.id = c;
							best.x = nx;
							best.y = ny;
						}
					}
				}
				if (best.id>0)
					return Entity(6, best.x, best.y);
			}
		}

		// 敵の動きを制限する敵落石
		if (game.me.spell >= game.spellcost[2] && !rac.empty()
			&& be.size() - rac.size() == 0){

			Field entitymap(game.enemy.field.width, game.enemy.field.height);
			entitymap.setEntity(game.enemy.dog);
			entitymap.setEntity(game.enemy.ninja);
			entitymap.setEntity(game.enemy.soul);

			Entity e;
			for (NinjaAction &na : rac){
				int lx, ly, hx, hy, x, y;
				lx = na.x; ly = na.y;
				hx = na.sx;	hy = na.sy;
				if (hx < lx) swap(lx, hx);
				if (hy < ly) swap(ly, hy);
				if (1 < lx)lx--;
				if (1 < ly)ly--;
				if (hx < game.enemy.field.width - 2) hx++;
				if (hy < game.enemy.field.height - 2) hy++;
				for (x = lx; x <= hx; x++)
					for (y = hy; y <= hy; y++){
						if (!entitymap[x][y]){
							PlayerStatus ps = game.enemy;
							ps.fieldOverride('O', x, y);
							if (na.act(ps,&e) & 1){
								predictDog(ps, e);
								if (ps.isDogHere(e.x, e.y)){
									return Entity(2,x,y);
								}
							}
							
						}
					}
				
			}

		}
	}
	//if (0 <= perhaps.id)
	//	return perhaps;

	// 岩砕き
	// TODO:条件debug用
	//if (game.spellcost[4] <= 2 && game.me.spell >= 8){
	if (game.spellcost[4] <= 2 && game.me.spell >= 6 + game.spellcost[4]*3){
		vector<Entity> dog = game.enemy.dog; // copy
		Field dist = createDistanceField(game.enemy.ninja, game.enemy.field);
		vector<Entity> ve;
		
		int x, y;
		// TODO:岩隣接を全部列挙?
		Entity far(0, 0, 0);
		for (x = 1; x < game.enemy.field.width - 1; x++)
			for (y = 1; y < game.enemy.field.width - 1; y++)
				if (dist[x][y] != 999 && far.id < dist[x][y] &&
					dist.roundsum4(x, y, 999) > 0){
					far.id = dist[x][y]; 
					far.x = x; far.y = y;
				}
		dog.push_back(far);
				
		for (Entity &e : dog){
			//e.id = dist[e.x][e.y];
			//if (dist[e.x][e.y]< 25) continue;
			int u = dist[e.x][e.y];
			if (game.enemy.field[e.x - 1][e.y] == 'O' && (
				dist[e.x - 2][e.y] < u - 24 ||
				dist[e.x - 1][e.y - 1] < u - 24 ||
				dist[e.x - 1][e.y + 1] < u - 24)){
				ve.push_back(Entity(dist[e.x - 2][e.y] - u, e.x - 1, e.y));
				ve.push_back(Entity(dist[e.x - 1][e.y - 1] - u, e.x - 1, e.y));
				ve.push_back(Entity(dist[e.x - 1][e.y + 1] - u, e.x - 1, e.y));
			}
			if (game.enemy.field[e.x + 1][e.y] == 'O' && (
				dist[e.x + 2][e.y] < u - 24 ||
				dist[e.x + 1][e.y - 1] < u - 24 ||
				dist[e.x + 1][e.y + 1] < u - 24)){
				ve.push_back(Entity(dist[e.x + 2][e.y] - u, e.x + 1, e.y));
				ve.push_back(Entity(dist[e.x + 1][e.y - 1] - u, e.x + 1, e.y));
				ve.push_back(Entity(dist[e.x + 1][e.y + 1] - u, e.x + 1, e.y));
			}
			if (game.enemy.field[e.x][e.y - 1] == 'O' && (
				dist[e.x][e.y - 2] < u - 24 ||
				dist[e.x - 1][e.y - 1] < u - 24 ||
				dist[e.x + 1][e.y - 1] < u - 24)){
				ve.push_back(Entity(dist[e.x][e.y - 2] - u, e.x, e.y - 1));
				ve.push_back(Entity(dist[e.x - 1][e.y - 1] - u, e.x, e.y - 1));
				ve.push_back(Entity(dist[e.x + 1][e.y - 1] - u, e.x, e.y - 1));
			}
			if (game.enemy.field[e.x][e.y + 1] == 'O' && (
				dist[e.x][e.y + 2] < u - 24 ||
				dist[e.x - 1][e.y + 1] < u - 24 ||
				dist[e.x + 1][e.y + 1] < u - 24)){
				ve.push_back(Entity(dist[e.x][e.y + 2] - u, e.x, e.y + 1));
				ve.push_back(Entity(dist[e.x - 1][e.y + 1] - u, e.x, e.y + 1));
				ve.push_back(Entity(dist[e.x + 1][e.y + 1] - u, e.x, e.y + 1));
			}
		}
		if (!ve.empty()){
			sort(ve.begin(), ve.end());
			return Entity(4, ve[0].x, ve[0].y);
		}
	}

	return Entity(-1, 0, 0);
}

// 分身を置く位置を決める
// resultに最も遠い位置を入れておく
void calcDupPos(Entity &result,PlayerStatus &ps,Entity &from){
	int x, y, max;
	// result＋距離3で置ける位置(TODO:3だと石で潰される)
	// TODO:評価の見直し
	vector<Entity> vc;

	vc.push_back(from);
	Field distfield = createDistanceField(vc, ps.field);
	vc.clear();

	if (ps.field[result.x][result.y]=='_')
		vc.push_back(result);

	for (int j = 3; j <= 4; j++)
		for (int i = 0; i <= j; i++){
			x = from.x - i;
			y = from.y - (j - i);
			if (0 < x && x < game.me.field.width - 1 && 0 < y && y < game.me.field.height - 1 &&
				distfield[x][y] != 999) vc.push_back(Entity(0, x, y));
			x = from.x + i;
			y = from.y - (j - i);
			if (0 < x && x < game.me.field.width - 1 && 0 < y && y < game.me.field.height - 1 &&
				distfield[x][y] != 999) vc.push_back(Entity(0, x, y));
			x = from.x - i;
			y = from.y + (j - i);
			if (0 < x && x < game.me.field.width - 1 && 0 < y && y < game.me.field.height - 1 &&
				distfield[x][y] != 999) vc.push_back(Entity(0, x, y));
			x = from.x + i;
			y = from.y + (j - i);
			if (0 < x && x < game.me.field.width - 1 && 0 < y && y < game.me.field.height - 1 &&
				distfield[x][y] != 999) vc.push_back(Entity(0, x, y));
		}
	x = 1; y = 1;
	if (distfield[x][y] != 999) vc.push_back(Entity(0, x, y));
	x = 1; y = game.me.field.height - 2;
	if (distfield[x][y] != 999) vc.push_back(Entity(0, x, y));
	x = game.me.field.width - 2; y = 1;
	if (distfield[x][y] != 999) vc.push_back(Entity(0, x, y));
	x = game.me.field.width - 2; y = game.me.field.height - 2;
	if (distfield[x][y] != 999) vc.push_back(Entity(0, x, y));

	oserr << "vcsize:" << vc.size() << endl;

	max = 99; // min
	for (Entity &e : vc){
		int c = 0;
		// MEMO:need setAllAction
		PlayerStatus ps = game.me;
		predictDog(ps, e);
		for (x = -2; x <= 2; x++)
			for (y = -2; y <= 2; y++){
				if (n1dist(x, y, 0, 0) <= 3 && 
					ps.isDogHere(from.x + x, from.y + y))c++;
			}
		if (c < max){
			max = c;
			result.x = e.x;
			result.y = e.y;
		}
	}
}

void setAllAction(vector<NinjaAction> &v,int x,int y,int walk){
	int i,j,l,n;
	v.clear();
	v.push_back(NinjaAction(x,y));
	l = 0; n = 1;
	for (i = 0; i < walk; i++){
		for (j = l; j < l + n; j++){
			NinjaAction na = v[j];
			v.push_back(na);
			v.back().moveDown();
			v.push_back(na);
			v.back().moveUp();
			v.push_back(na);
			v.back().moveLeft();
			v.push_back(na);
			v.back().moveRight();
		}
		l += n;
		n *= 4;
	}
}

// 道パターンを広く浅く列挙
int calcNinjaLongRange(Entity &first,PlayerStatus &psnow,Entity &spell,
	vector<NinjaAction> &outvna,int length,int walk,bool *spellchk){
	// TODO:length
	// 
	int i;
	int cnt;
	int maxturn = 0;

	bool ableEnemy = game.enemy.spell >= game.spellcost[2] || game.enemy.spell >= game.spellcost[6];
	bool ableMe = game.me.spell >= game.spellcost[3] || game.me.spell >= game.spellcost[5];

	vector<NinjaAction> vc;

	Entity lastq;
	priority_queue<Entity> prq;       // next (priority,idx,scorefinal)
	vector<PlayerStatus> vps;         // status (playerStatusのヴェクタはデカい)
	vector<Entity> ve;                // position,score
	vector<vector<NinjaAction>> navv; // command
	vector<Field> scoreField;         // scorefield(memo:ダイエット)
cnlr_redo:
	vps.clear(); vps.clear(); ve.clear(); navv.clear(); scoreField.clear();

	vps.push_back(psnow);
	ve.push_back(first);
	ve.back().id = 0;
	navv.push_back(vector<NinjaAction>(0));
	scoreField.push_back(Field());
	psnow.calcScore(scoreField.back(), false, false);

	prq.push(Entity(0, 0, 0));

	bool reachSoul = false;

	for (cnt = 0; cnt < 4500 && !prq.empty();){ // (reachSoul?4500:7000)
		Entity et = prq.top(); prq.pop();
		int id = et.x;
		int etc = et.y;

		// memo:参照型NG
		PlayerStatus pps = vps[id];
		Entity nin = ve[id];
		vector<NinjaAction> nav = navv[id];

		Field scf = scoreField[id];
		
		vc.clear();
		if (nav.size() == 0 && spell.id == 0)
			setAllAction(vc, nin.x, nin.y, 3);
		else
			setAllAction(vc, nin.x, nin.y, 2);

		for (NinjaAction &cmd : vc){
			bool fail = false;
			int soul = 0;
			int risk;
			PlayerStatus ps = pps;
			Entity nxt = cmd.toEntity();

			cmd.test(ps, Entity(cmd.sx, cmd.sy), soul, soul, risk); // MEMO:act統合したい soul=dummy

			int res = cmd.act(ps);
			if (res & 1) continue; // fail
			soul = (res & 28)>>2;

			if (nav.size() == 0){
				if (spell.id == 5)
					predictDog(ps, spell);
				else
					predictDog(ps, nxt);
			}
			else{
				predictDog(ps, nxt);
			}

			
			for (Entity &d : ps.dog){ // 捕まる
				if (d.x == nxt.x && d.y == nxt.y) {
					fail = true; break;
				}
			}
			if (fail) continue;
			if (risk && ableMe) continue;

			// TODO:評価
			int score = nin.id + soul * 100 / (nav.size()+1);// -1; // stepfunc(6-etc*2)

			reachSoul |= !!soul;

			cmd.score = scf[cmd.x][cmd.y];

			navv.push_back(nav);
			navv.back().push_back(cmd);

			nxt.id = score;
			ve.push_back(nxt);
			
			vps.push_back(ps);

			scoreField.push_back(Field());
			ps.calcAbleSoul();
			ps.calcScore(scoreField.back(), false, false);

			prq.push(Entity(//(score + n1dist(first.x, first.y, cmd.x, cmd.y) - (nav.size()+1)*2)*100
				-limit(nav.size(), 0, 2) * 20 // + score * 20
				+ scf[cmd.x][cmd.y] + score / 2
				, vps.size() - 1, scf[cmd.x][cmd.y] + scoreField.back()[cmd.x][cmd.y]
				+ ((score * 10) + 2*n1dist(first.x, first.y, cmd.x, cmd.y))));
			cnt++;

			if (nav.size() + 1 > maxturn) maxturn = nav.size() + 1;

		}

	}

	int prqsize = 0;
	list<Entity> prl;
	while (!prq.empty()){
		prl.push_back(prq.top());
		i = prq.top().x;
		prl.back().id = -prl.back().y - game.scorefieldMe[navv[i][0].x][navv[i][0].y];//-ve[e.x].y;
		prq.pop();
		prqsize++;
	}

	oserr << "prqs = " << prqsize << " / maxturn = " << maxturn << endl;

	prl.sort();

	outvna.clear();

	while (!prl.empty()){
		bool flg = false;
#ifdef __GNUC__
		Entity e = prl.front();
#else
		Entity &e = prl.front();
#endif

		NinjaAction &na = navv[e.x][0];

		for (NinjaAction &n : outvna){
			if (na.equals(n)){ flg = true; break; }
		}

		if (!flg){
			outvna.push_back(na);

			oserr << e.tostring() << endl;
			for (NinjaAction &na : navv[e.x]){
				oserr << na << " -> ";
			}
			oserr << endl;
		}
		prl.pop_front();
	}

	if (prqsize <= 100){ //  && maxturn < 3
		// TODO:雷<高速パターン
		if (!spellchk[0] && (game.spellcost[0] <= game.spellcost[5])){ // || spellchk[5]
			return 0;
		}
		if (!spellchk[5]){
			return 5;
		}
	}

	if (outvna.size() <= 3){

		//if (ableEnemy && ableMe){
		//	ableMe = ableEnemy = false;
		//	goto cnlr_redo;
		//}

		if (!ve.empty()){ //  && spell.id!=0
			//// 単純採用(保留(´・ω・｀)
			//oserr << "vesize:" << ve.size() << endl;
			//vector<Entity> v;
			//for (i = 0; i < ve.size(); i++)
			//	if (!navv[i].empty())
			//		v.push_back(Entity(-game.scorefieldMe[navv[i][0].x][navv[i][0].y], i, 0));
			//sort(v.begin(), v.end());
			//
			//for (i = 0; outvna.size() <= 3 && i<v.size(); i++){
			//	bool flg = false;
			//	if (navv[v[i].x].empty()) break;
			//
			//	NinjaAction &na = navv[v[i].x][0];
			//	for (NinjaAction &n : outvna){
			//		if (na.equals(n)){ flg = true; break; }
			//	}
			//	if (!flg){
			//		outvna.push_back(na);
			//	}
			//}

			// 生存したものを採用
			oserr << "vesize:" << ve.size() << endl;
			vector<Entity> v;
			for (i = 0; i < ve.size(); i++)
				v.push_back(Entity(-navv[i].size(), i, 0));
			sort(v.begin(), v.end());

			for (i = 0; outvna.size() < 3 && i<v.size(); i++){
				bool flg = false;
				if (navv[v[i].x].empty()) break;

				NinjaAction &na = navv[v[i].x][0];
				for (NinjaAction &n : outvna){
					if (na.equals(n)){ flg = true; break; }
				}
				if (!flg){
					outvna.push_back(na);
				}
			}
		}
	}

	return -1;
	
}

void calcNinjaMove(){
	int x, y, ninidx,i, j;
	int movenum = 2; // 2 or 3
    vector<NinjaAction> ae;
	vector<Entity> be;
	vector<Entity> xe;
    queue<NinjaAction> qe;
	Field checker(7, 7);
	Entity drill;

	bool spellchk[8];
	Entity spell(-1, 0, 0);
	vector<NinjaAction> result;
	for (i = 0; i < 8; i++)
		spellchk[i] = game.me.spell < game.spellcost[i]; // t=使えない

	Field dogMap(game.me.field.width, game.me.field.height);
	game.me.setDogMap(dogMap);

	// MEMO::need sort ninja?

	// 回転斬り
	if (!spellchk[7]){ // game.spellcost[7] * 3 / 2 >= game.me.spell
		for (i = 0; i < game.me.ninja.size(); i++){
			Entity &e = game.me.ninja[i];
			if (dogMap.roundsum(e.x, e.y) >= (game.spellcost[7] + 4) / 4){
				spellchk[7] = true;// 回転斬り
				spell.id = 7;
				spell.x = i;
				oserr << "spellninja " << i << endl;
				oserr << "spell_round[7] called." << endl;
				break;
			}
		}
	}


	// quickガンガン使おう
	if (!spellchk[0] && game.spellcost[0] <= 2 && gameLoopCnt * 5 / 3 < game.me.spell){
		spell.id = 0;
	}

	for (ninidx = 0; ninidx < game.me.ninja.size(); ninidx++){
		Entity &ninja = game.me.ninja[ninidx];
		movenum = (spell.id != 0) ? 2 : 3;
		
		ae.clear(); be.clear(); xe.clear();
		checker.fill(0);
		oserr << "ninja? > ";
		oserr << ninja.tostring() << endl;

		qe.push(NinjaAction(ninja.x, ninja.y));

		PlayerStatus pspr = game.me; // pre
		if (spell.id == 7)
			pspr.attack(spell.x);
		for (j = 0; j < ninidx; j++){ // 前のninja実行
			result[j].act(pspr);
			pspr.ninja[j].x = result[j].x;
			pspr.ninja[j].y = result[j].y;
		}
		{
			int k;
			k = calcNinjaLongRange(ninja, pspr, spell, ae, 10, 2, spellchk);
			switch (k){ // TODO:仮
			case 0:
				goto cnm_spellready_quick;
			case 5:
				goto cnm_spellready_dupme;
			}
		}

		oserr << "ae:" << endl;
		for (NinjaAction &na : ae)
			oserr << (na) << " " << (na.vx) << "," << (na.vy) << endl;

		for (NinjaAction &na : ae){
			int soul, fail, stone, risk;

			PlayerStatus pspd = pspr; // hint! pspr

			na.act(pspd);
			if (spell.id != 5){
				pspd.ninja[ninja.id] = na.toEntity(ninja.id);
				predictDog(pspd);
			}
			else
				predictDog(pspd, spell); // 犬はspellと間違える

			if (pspd.isDogHere(na.x, na.y)) continue;

			stone = na.test(game.me, ninja, soul, fail, risk);
			xe.push_back(Entity(-soul, stone, risk, &na));
		}

		//if (!xe.empty()){
		//	if (dogMap.roundsum12(ninja.x, ninja.y)){
		//		stable_sort(xe.begin(), xe.end(),
		//			[](const Entity &e1, const Entity &e2){
		//			return e1.id != e2.id ? (e1.id < e2.id) : (e1.x < e2.x); });
		//	}
		//	else{
		//		stable_sort(xe.begin(), xe.end());
		//	}
		//}

		oserr << "xe:" << endl;
		for (Entity &e : xe){
			NinjaAction *na = (NinjaAction*)(e.link);
			oserr << e.tostring()
				<< " " << (na->vx) << "," << (na->vy) << endl;
		}

		if (1<xe.size()){
			queue<Entity> q;
			Entity &te = xe[0];
			NinjaAction *ta = (NinjaAction*)(te.link);
			for (Entity &e : xe){
				NinjaAction *na = (NinjaAction*)(e.link);
				if (ta->vx == na->vx && ta->vy == na->vy)
					be.push_back(e);
				else
					q.push(e);
			}

			stable_sort(be.begin(), be.end(),
				[](const Entity &e1, const Entity &e2){
				return e1.id != e2.id ? (e1.id < e2.id) : (e1.y < e2.y); });

			while (!q.empty()){
				be.push_back(q.front());
				q.pop();
			}
		}
		else{
			be = xe;
		}

		oserr << "be:" << endl;
		for (Entity &e : be){
			NinjaAction *na = (NinjaAction*)(e.link);
			oserr << e.tostring()
				<< " v " << (na->vx) << "," << (na->vy) << endl;
		}


		oserr << "calc ok! besize:" << be.size() << endl;
		// 動かないという選択しか無い
		if (be.size() == 1 && ((NinjaAction*)(be[0].link))->cmdsize() == 0){
			//goto cnm_spellready;
			if (((game.me.field[ninja.x - 1][ninja.y] != '_')
				+ (game.me.field[ninja.x + 1][ninja.y] != '_')
				+ (game.me.field[ninja.x][ninja.y - 1] != '_')
				+ (game.me.field[ninja.x][ninja.y + 1] != '_') >= 3) && !spellchk[3]){
				goto cnm_spellready_drilme;
			}
		}
		// 数少ない選択肢のうち...
		if (!be.empty() && spell.id == -1 && !spellchk[3] // && be.size() <= 4
			&& dogMap.roundsum4(ninja.x,ninja.y)
			&& trustmode != 1){
			// 岩を押すアクション
			int n = 0;
			bool first = true;
			Entity rock;
			for (Entity &e : be){
				NinjaAction *nap = ((NinjaAction*)(e.link));
				Entity r = nap->testRockPos(game.me, ninja.id);
				if (r.id == 1){
					if (first) rock = r;
					n++;
				}else if (first){
					// 選んだものが岩を押さないなら崩す意味は無い
					n = 0; break;
				}
				first = false;
			}
			if (n && be.size() - n <= 1
				&& game.enemy.spell >= game.spellcost[2]){
				spellchk[3] = true;
				//goto cnm_spellready_drilme; // MEMO:下手な岩選択するとなすすべなしになる
				spell.id = 3; // 岩砕き
				spell.x = rock.x;
				spell.y = rock.y;
				// memo:redoしない
				//game.me.fieldUndo();
				//result.clear(); i = -1; continue; // reloop
			}
			else{
				int d = 0;
				for (Entity &e : be){
					NinjaAction *nap = ((NinjaAction*)(e.link));
					if (nap->cmdsize() == 0) continue;
					if (d == 0){ d = nap->history.front(); continue; }
					if (d != nap->history.front()){ d = 0; break; }
				}
				
				if (d){
					// 岩押さない(かも)だけど岩落とされるかも
					//Entity &e = be[0];
					NinjaAction *nap = ((NinjaAction*)(be[0].link));
					if (0 < nap->cmdsize()){
						int vx = 0, vy = 0;
						switch (d){
						case 'L':
							vx = -1; vy = 0; break;
						case 'R':
							vx = 1; vy = 0; break;
						case 'U':
							vx = 0; vy = -1; break;
						case 'D':
							vx = 0; vy = 1; break;
						}
						if (game.me.field[nap->sx + vx * 2][nap->sy + vy * 2] == 'O'
							&& game.enemy.spell >= game.spellcost[2]){
							spellchk[3] = true;
							spell.id = 3; // 岩砕き
							spell.x = nap->sx + vx * 2;
							spell.y = nap->sy + vy * 2;
						}
					}
				}
			}

		}

		if (be.empty()){
cnm_spellready:
			// 行動できないので技を使う

			if (((game.me.field[ninja.x - 1][ninja.y] != '_') // MEMO:なすすべなしより、
				+ (game.me.field[ninja.x + 1][ninja.y] != '_') // 犬に囲まれていることがわかる
				+ (game.me.field[ninja.x][ninja.y - 1] != '_')
				+ (game.me.field[ninja.x][ninja.y + 1] != '_') >= 3) && !spellchk[3]){
cnm_spellready_drilme:
				game.me.fieldUndo();
				spellchk[3] = true; // 雷撃
				vector<Entity> round;
				if (game.me.field[ninja.x - 1][ninja.y] == 'O')
					round.push_back(Entity(-game.scorefieldMe[ninja.x - 1][ninja.y], ninja.x - 1, ninja.y));
				if (game.me.field[ninja.x + 1][ninja.y] == 'O')
					round.push_back(Entity(-game.scorefieldMe[ninja.x + 1][ninja.y], ninja.x + 1, ninja.y));
				if (game.me.field[ninja.x][ninja.y - 1] == 'O')
					round.push_back(Entity(-game.scorefieldMe[ninja.x][ninja.y - 1], ninja.x, ninja.y - 1));
				if (game.me.field[ninja.x][ninja.y + 1] == 'O')
					round.push_back(Entity(-game.scorefieldMe[ninja.x][ninja.y + 1], ninja.x, ninja.y + 1));
				sort(round.begin(), round.end());
				spell = round[0];
				spell.id = 3;
				game.me.fieldOverride('_', spell.x, spell.y);

				oserr << "spellpos->(" << spell.x << "," << spell.y << ")" << endl;
				oserr << "spell_drill_me[3] called...redo!" << endl;
				result.clear(); ninidx = -1; continue; // reloop

			}else if ((spellchk[0] || game.spellcost[0] > game.spellcost[5])
				&& !spellchk[5]){
cnm_spellready_dupme:
				oserr << "dup search begin" << endl;
				spellchk[5] = true; // 分身
				// 最も遠い場所＋距離3で置ける位置(TODO:3だと石で潰される)
				// TODO:評価の見直し
				Field dist = createDistanceField(game.me.ninja, game.me.field);
				int max = -1;
				for (x = 0; x < dist.width; x++)
					for (y = 0; y < dist.height; y++)
						if (max < dist[x][y] && dist[x][y] != 999){
							for (Entity &e : game.me.ninja)
								if (n1dist(e.x, e.y, x, y) < 4){ // 岩で潰さないように
									goto cnm_spelldupme_lpcontinue;
								}
							spell.x = x; spell.y = y; max = dist[x][y];
cnm_spelldupme_lpcontinue:
							;
						}

				calcDupPos(spell, game.me, ninja);


				spell.id = 5;
				oserr << "spellpos->(" << spell.x << "," << spell.y << ") min-" << max << endl;
				oserr << "spell_dup_me[5] called...redo!" << endl;
				game.me.fieldUndo();
				result.clear(); ninidx = -1; continue; // reloop

			}
			else if (!spellchk[0]){
cnm_spellready_quick:
				spellchk[0] = true; // 高速
				spell.id = 0;
				oserr << "spell_quick[0] called...redo!" << endl;
				game.me.fieldUndo();
				result.clear(); ninidx = -1; continue; // reloop
			}
			
			// なすすべなし
			oserr << "act:" << "(;_;)" << endl;
			result.push_back(NinjaAction());
			continue;
		}

		//cout << (*(NinjaAction*)(be[0].link)) << endl;
		result.push_back(NinjaAction(*(NinjaAction*)(be[0].link)));
		oserr << "act:" << (*(NinjaAction*)(be[0].link))<<" " << endl;
	}
	game.me.fieldUndo();
	
cnm_spell_redo:
	switch (spell.id){
	case 0: // quick
		if (result[0].cmdsize() <= 2 && result[1].cmdsize() <= 2){
			spell.id = -1;
			oserr << "break quick." << endl;
			goto cnm_spell_redo;
		}
		cout << "3" << endl;
		cout << "0" << endl;
		break;
	case 1: // mstone
	case 2: // estone
	case 3: // mflash
	case 4: // eflash
	case 5: // mdup
	case 6: // edup
		cout << "3" << endl;
		cout << spell.id << " " << spell.y << " " << spell.x << endl;
		break;
	case 7: // round
		cout << "3" << endl;
		cout << spell.id << " " << spell.x << endl;
		break;
	default:
		// 攻撃を試みる
		if (!trustmode){
			oserr << "attack?" << endl;
			Entity atk = calcTry2Attack();
			if (0 <= atk.id){
				spell = atk;
				goto cnm_spell_redo;
			}

		}

		// アカン
		cout << "2" << endl;
	}
	for (NinjaAction &na : result)
		cout << na << endl;

}


bool gameLoop(){
	oserr << "+++ gameLoop" << gameLoopCnt << " Begin +++" << endl;
    game.reset();

    if (0<consoleLoad()) return false;
    game.me.calcScore(game.scorefieldMe,true);
	game.scorefieldMe.eprintint();
	game.enemy.calcScore(game.scorefieldEnemy, false);
	game.scorefieldEnemy.eprintint();

    calcNinjaMove();

	gameLoopCnt++;

    return true;
}

int main(int argc,char **argv){
	debugmode = false;
	randommode = false;
	trustmode = 0;
	int i;
	for (i = 1; i < argc; i++){
		switch (argv[i][0]){
		case 'D':
			debugmode = true;
			break;
		case 'R':
			randommode = true;
			break;
		case 'T':
			trustmode = 1;
			break;
		case 'U':
			trustmode = 2;
			break;
		}
	}
	if (randommode)
		cerr << "Random Mode" << endl;
	
	cerr << "GoodLuck&HaveFun!" << endl;
    cout<<"Maiha Mai"<<endl;
    while(gameLoop());
    return 0;
}