Created
December 11, 2015 14:51
-
-
Save kngwyu/496a43655b91d961b6ba to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstdio> | |
#include <cmath> | |
#include <cstring> | |
#include <ctime> | |
#include <iostream> | |
#include <algorithm> | |
#include <set> | |
#include <vector> | |
#include <tuple> | |
#include <sstream> | |
#include <typeinfo> | |
#include <fstream> | |
#include <random> | |
#include <map> | |
using namespace std; | |
//敵の情報を保存するデータ構造 | |
struct Creep { | |
int unique_id; | |
int health; | |
int column; | |
int row; | |
}; | |
//武器となるTowerの情報を保存するデータ構造 | |
struct Tower { | |
int range; | |
int damage; | |
int cost; | |
int numb; | |
}; | |
bool cmp1( const Tower& left, const Tower& right ) { | |
return left.damage == right.damage ? left.cost > right.cost : left.damage > right.damage; | |
} | |
bool cmp2( const Tower& left, const Tower& right ) { | |
return left.range == right.range ? left.cost > right.cost : left.range > right.range; | |
} | |
bool cmp3( const Tower& left, const Tower& right ) { | |
return left.cost == right.cost ? left.range > right.range : left.cost > right.cost; | |
} | |
int main() { | |
int N;// 盤面の1辺の長さ | |
cin >> N; | |
int money;// 所持金 | |
cin >> money; | |
// 盤面の情報を取得する | |
vector<string> board(N); | |
for (int i = 0; i < N; ++i) { | |
cin >> board[i]; | |
} | |
int score[61][61]; | |
for(int i=0;i<N;i++){ | |
for(int j=0;j<N;j++){ | |
score[i][j] = 0; | |
} | |
} | |
int creepHealth; | |
cin >> creepHealth;// Creepの初期体力 | |
int creepMoney; | |
cin >> creepMoney;// Creepを倒すともらえるお金 | |
int M; | |
cin >> M;//Towerの種類 | |
int lcost = 1000000; | |
vector<Tower> towers; | |
for (int i = 0; i < M; ++i) { | |
Tower t; | |
cin >> t.range; | |
cin >> t.damage; | |
cin >> t.cost; | |
t.numb = i; | |
lcost = min(lcost, t.cost); | |
towers.push_back(t); | |
} | |
// ここにTowerを建てたかどうか保存しています | |
vector<vector<bool>> built(N, vector<bool>(N, false)); | |
//縦がi | |
//baseまわりにscoreを足す | |
for(int i=0;i<N;i++){ | |
for(int j=0;j<N;j++){ | |
if(board[i][j] != '.' && board[i][j] != '#'){ | |
for(int k= -3;k<=3;k++){ | |
for(int l= -3;l<=3;l++){ | |
if(i+k < N && j+l < N && i+k >=0 && j+l >= 0 && !(l==0 && k==0)){ | |
if(board[i+k][j+l] == '#'){ | |
if(abs(k)<=2 && abs(l)<=2){ | |
score[i+k][j+l]+= 8; | |
}else{ | |
score[i+k][j+l]+= 4; | |
} | |
} | |
} | |
} | |
} | |
} | |
} | |
} | |
//入り口 | |
for(int i=0;i<N;i++){ | |
if(board[i][0]=='.'){ | |
for(int k= -2;k<=2;k++){ | |
for(int l= 0;l<=2;l++){ | |
if(i+k < N && i+k >= 0 && !(l==0 && k==0)){ | |
if(board[i+k][l] == '#'){ | |
score[i+k][l] += 2; | |
} | |
} | |
} | |
} | |
} | |
if(board[i][N-1]=='.'){ | |
for(int k= -2;k<=2;k++){ | |
for(int l= -3;l<=-1;l++){ | |
if(i+k < N && i+k >= 0 && !(l==0 && k==0)){ | |
if(board[i+k][N+l] == '#'){ | |
score[i+k][N+l] += 2; | |
} | |
} | |
} | |
} | |
} | |
} | |
for(int j=0;j<N;j++){ | |
if(board[0][j]=='.'){ | |
for(int k= -2;k<=2;k++){ | |
for(int l= 0;l<=2;l++){ | |
if(j+k < N && j+k >= 0 && !(l==0 && k==0)){ | |
if(board[l][j+k] == '#'){ | |
score[l][j+k] += 2; | |
} | |
} | |
} | |
} | |
} | |
if(board[N-1][j]=='.'){ | |
for(int k= -2;k<=2;k++){ | |
for(int l= -3;l<=-1;l++){ | |
if(j+k < N && j+k >= 0 && !(l==0 && k==0)){ | |
if(board[l+N][j+k] == '#'){ | |
score[l+N][j+k]+= 2; | |
} | |
} | |
} | |
} | |
} | |
} | |
// Start the Game!! | |
int basehp[61][2001]; | |
for(int i=0;i<61;i++){ | |
for(int j=0;j<2001;j++){ | |
basehp[i][j] = 0; | |
} | |
} | |
for (int turn = 0; turn < 2000; ++turn) { | |
cin >> money; | |
int creepNum; | |
cin >> creepNum;// 盤面上に存在する敵の数 | |
int warnlevel = 0; | |
vector<Creep> creeps; | |
for (int i = 0; i < creepNum; ++i) { | |
Creep crp; | |
cin >> crp.unique_id; | |
cin >> crp.health; | |
cin >> crp.column; | |
cin >> crp.row; | |
int j = crp.column;//列 | |
int k = crp.row;//行 | |
int warnmemo[2]; | |
for(int l= -5;l<=5;l++){ | |
for(int m= -5;m<=5;m++){ | |
if(j+m < N && k+l < N && j+m >=0 && k+l >= 0 && !(l==0 && m==0) ){ | |
if(board[k+l][j+m] == '#'){ | |
if(abs(l)<=1 && abs(m)<=1){ | |
score[k+l][j+m]+= 4; | |
}else if(abs(l)<=2 && abs(m)<=2){ | |
score[k+l][j+m]+= 2; | |
} | |
}else if(board[k+l][j+m] != '.' && warnlevel != 2){ | |
if(abs(l)<=3 && abs(m)<=3){ | |
warnlevel += 2; | |
warnmemo[0] = k+l; | |
warnmemo[1] = j+m; | |
}else if(abs(l)<=5 && abs(m)<=5){ | |
warnlevel += 1; | |
warnmemo[0] = k+l; | |
warnmemo[1] = j+m; | |
} | |
} | |
} | |
} | |
} | |
if(warnlevel != 0){ | |
int p = warnmemo[0]; | |
int q = warnmemo[1]; | |
for(int k= -5;k<=5;k++){ | |
for(int l= -5;l<=5;l++){ | |
if(p+k < N && q+l < N && p+k >=0 && q+l >= 0 && !(l==0 && k==0)){ | |
if(board[p+k][q+l] == '#'){ | |
if(abs(k)<=2 && abs(l)<=2){ | |
score[p+k][q+l]+= 8; | |
}else if(abs(k)<=3 && abs(l)<=3){ | |
score[p+k][q+l]+= 2; | |
}else{ | |
score[p+k][q+l]+= 1; | |
} | |
} | |
} | |
} | |
} | |
} | |
creeps.push_back(crp); | |
} | |
int baseNum; | |
cin >> baseNum;// Base の数 | |
for (int i = 0; i < baseNum; ++i) { | |
int hp; | |
cin >> hp; | |
basehp[i][turn] = hp; | |
} | |
//安定している状態では新しくタワーを作らない | |
bool hpkanri = true; | |
if(turn>=150){ | |
for(int i = 0; i < baseNum; i++){ | |
for(int j=1;j<=50;j++){ | |
int k = basehp[i][turn-j] - basehp[i][turn]; | |
if(k!=0){ | |
hpkanri = false; | |
goto KOUGEKI; | |
} | |
} | |
} | |
} | |
KOUGEKI: | |
vector<tuple<int, int, int>> ret;// 出力したい結果をretに保存する | |
// 保存しておいた情報を出力 | |
int buildtower=0; | |
int nanimosinai = 0; | |
int okozukai; | |
int atacknum = money/lcost; | |
if(atacknum == 0){ | |
okozukai = 0; | |
}else if(atacknum == 1 || atacknum ==2){ | |
okozukai = money; | |
}else if(atacknum == 3 || atacknum == 4){ | |
if(warnlevel >=2){ | |
okozukai = money; | |
}else{ | |
okozukai = money - lcost*2; | |
} | |
}else{ | |
okozukai = min(lcost*warnlevel, money); | |
} | |
if(((hpkanri == false || warnlevel != 0) && turn>=100) || turn < 100){ | |
while(okozukai >= lcost){ | |
int maxscore=0; | |
int Muki = buildtower%2; | |
int row, column,kind;//builtの初期値はfalse→0 | |
//rowが縦columnが横 | |
if(Muki==0){ | |
for(int i=0;i<N;i++){ | |
for(int j=0;j<N;j++){ | |
if(built[i][j]==false && board[i][j]=='#'){ | |
if(score[i][j] > maxscore){ | |
row = i; | |
column = j; | |
maxscore = score[i][j]; | |
} | |
} | |
} | |
} | |
}else { | |
for(int i=N-1;i>=0;--i){ | |
for(int j=N-1;j>=0;--j){ | |
if(built[i][j]==false && board[i][j]=='#'){ | |
if(score[i][j] > maxscore){ | |
row = i; | |
column = j; | |
maxscore = score[i][j]; | |
} | |
} | |
} | |
} | |
} | |
if(maxscore==0){ | |
break; | |
} | |
built[row][column] = true; | |
if(okozukai>=lcost*2 && warnlevel >= 3){ | |
//range順にソート | |
sort(towers.begin(), towers.end(), cmp2); | |
for(int i=0;i<M;i++){ | |
if(okozukai>=towers[i].cost){ | |
kind = towers[i].numb; | |
okozukai = okozukai - towers[i].cost; | |
break; | |
} | |
} | |
}else{ | |
//安い順にsort | |
sort(towers.begin(), towers.end(), cmp3); | |
for(int i=0;i<M;i++){ | |
if(okozukai>=towers[i].cost){ | |
kind = towers[i].numb; | |
okozukai = okozukai - towers[i].cost; | |
break; | |
} | |
} | |
} | |
ret.push_back(make_tuple(column, row, kind)); | |
built[row][column] = true; | |
nanimosinai += 1; | |
buildtower +=1; | |
} | |
} | |
if(nanimosinai==0){ | |
cout << "-1" << endl; | |
}else{ | |
cout << ret.size() << endl; | |
for (int i = 0; i < ret.size(); ++i) { | |
cout << get<0>(ret[i]) << " " << get<1>(ret[i]) << " " << get<2>(ret[i]) | |
<< endl; | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment