Last active
August 29, 2015 14:07
-
-
Save Yazaten/f55a2c4abc6b73fb837d to your computer and use it in GitHub Desktop.
30Cr 分だけ盤面の状態を列挙する
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<stdio.h> | |
#include<time.h> | |
#define DROP_SUM 30 | |
#define Attack_Drop 8 //攻撃色ドロップの数 | |
#define Line_Skill 5 //列強化の覚醒の個数 | |
int AnswerBoard[5][6]; | |
double MaxiScore=-1; | |
//次の盤面を求める。次の盤面があれば1、なければ0を返す | |
int next_board(int board[5][6]){ | |
int i, j; | |
int a[31] = {0}; | |
int sum; | |
for(i = 0; i < 5; i++){ | |
for(j = 0; j < 6; j++){ | |
a[6 * i + j] = board[i][j]; | |
} | |
} | |
do{ | |
sum = 0; | |
a[0]++; | |
for(i = 0; i < 30; i++){ | |
if(a[i] == 2){ | |
a[i] = 0, a[i + 1]++; | |
} | |
} | |
for(i = 0; i < 30; i++){ | |
sum += a[i]; | |
} | |
}while(sum != Attack_Drop && a[30] == 0); | |
for(i = 0; i < 5; i++){ | |
for(j = 0; j < 6; j++){ | |
board[i][j] = a[6 * i + j]; | |
} | |
} | |
if(a[30] == 0) return 1; | |
else return 0; | |
} | |
//mのドロップの配列vanishを計算する関数 | |
void vanish_drop(int board[5][6], int vanish[5][6], int m){ | |
int i, j; | |
//vanishを初期化 | |
for(i = 0; i < 5; i++){ | |
for(j = 0; j < 6; j++){ | |
vanish[i][j] = 0; | |
} | |
} | |
for(i = 0; i < 5; i++){ | |
for(j = 0; j < 4; j++){ | |
if(board[i][j] == board[i][j + 1] && board[i][j + 1] == board[i][j + 2] && board[i][j] == m){ | |
vanish[i][j] = vanish[i][j + 1] = vanish[i][j + 2] = 1; | |
} | |
} | |
} | |
for(i = 0; i < 3; i++){ | |
for(j = 0; j < 6; j++){ | |
if(board[i][j] == board[i + 1][j] && board[i + 1][j] == board[i + 2][j] && board[i][j] == m){ | |
vanish[i][j] = vanish[i + 1][j] = vanish[i + 2][j] = 1; | |
} | |
} | |
} | |
} | |
//隣接行列を求める関数 | |
void adjoin(int vanish[5][6], int ad[30][30]){ | |
int i, j; | |
for(i = 0; i < 30; i++){ | |
for(j = 0; j < 30; j++){ | |
ad[i][j] = 0; | |
} | |
} | |
for(i = 0; i < 5; i++){ | |
for(j = 0; j < 6; j++){ | |
if(i != 0){ | |
if(vanish[i][j] == 1 && vanish[i - 1][j] == 1){ | |
ad[6 * i + j][6 * (i - 1) + j] = ad[6 * (i - 1) + j][6 * i + j] = 1; | |
} | |
} | |
if(i != 4){ | |
if(vanish[i][j] == 1 && vanish[i + 1][j] == 1){ | |
ad[6 * i + j][6 * (i + 1) + j] = ad[6 * (i + 1) + j][6 * i + j] = 1; | |
} | |
} | |
if(j != 0){ | |
if(vanish[i][j] == 1 && vanish[i][j - 1] == 1){ | |
ad[6 * i + j][6 * i + j - 1] = ad[6 * i + j - 1][6 * i + j] = 1; | |
} | |
} | |
if(j != 5){ | |
if(vanish[i][j] == 1 && vanish[i][j + 1] == 1){ | |
ad[6 * i + j][6 * i + j + 1] = ad[6 * i + j + 1][6 * i + j] = 1; | |
} | |
} | |
} | |
} | |
} | |
//mと一緒に消えるドロップの個数を求める(m:配列を1列にしたときの番号) | |
int connect(int board[5][6], int vanish[5][6], int ad[30][30], int visited[], int m){ | |
int vanish_num = 0; | |
int j; | |
visited[m] = 1; | |
//消えるドロップを-1にしてvanishでは0にする | |
board[m / 6][m % 6] = -1; | |
vanish[m / 6][m % 6] = 0; | |
for(j = 0; j < 30; j++){ | |
if(ad[m][j] == 1 && visited[j] == 0){ | |
board[j / 6][j % 6] = -1; | |
vanish[j / 6][j % 6] = 0; | |
connect(board, vanish, ad, visited, j); | |
} | |
} | |
for(j = 0; j < 30; j++){ | |
vanish_num += visited[j]; | |
} | |
return vanish_num; | |
} | |
//aとbを交換 | |
void swap(int *a, int *b){ | |
int c; | |
c = *a; | |
*a = *b; | |
*b = c; | |
} | |
//ドロップを落とす関数 | |
void drop(int board[5][6]){ | |
int i, j, k; | |
for(k = 0; k < 5; k++){ | |
for(i = 0; i < 4; i++){ | |
for(j = 0; j < 6; j++){ | |
if(board[i + 1][j] == -1) swap(&board[i][j], &board[i + 1][j]); | |
} | |
} | |
} | |
} | |
double solve(int board[5][6]){ | |
int board_copy[5][6]; | |
int vanish[5][6]; //消える攻撃色ドロップ | |
int ad[30][30] = {0}; //隣接行列 | |
int visited[30]; //経路探索のときに通ったところを1、通ってないところを0 | |
int combo; //コンボ数 | |
int conne; //繋がってる個数 | |
int line; //列の数 | |
int flag; | |
double attack; //攻撃倍率 | |
int i,j,k,m; | |
//board_copyにboardをうつす | |
for(i = 0; i < 5; i++){ | |
for(j = 0; j < 6; j++){ | |
board_copy[i][j] = board[i][j]; | |
} | |
} | |
combo = 0; | |
line = 0; | |
attack = 0; | |
do{ | |
do{ | |
flag = 0; | |
//攻撃色のvanishを求める | |
vanish_drop(board_copy, vanish, 1); | |
//消えるドロップがあればflag=1 | |
for(i = 0; i < 5; i++){ | |
for(j = 0; j < 6; j++){ | |
if(vanish[i][j] == 1){ | |
flag = 1; break; | |
} | |
} | |
} | |
//vanishの隣接行列adを求める | |
adjoin(vanish, ad); | |
//消える攻撃色ドロップの個数を求め、攻撃倍率を計算する | |
do{ | |
//vanishが1の場所を探す | |
for(i = 0; i < 5; i++){ | |
for(j = 0; j < 6; j++){ | |
if(vanish[i][j] == 1){ | |
combo++; | |
//visitedを初期化 | |
for(k = 0; k < 30; k++){ | |
visited[k] = 0; | |
} | |
//board[i][j]と一緒に消えるドロップの個数を求める | |
conne = connect(board_copy, vanish, ad, visited, 6 * i + j); | |
//列の数を求める | |
for(m = 0; m < 5; m++){ | |
if(visited[6 * m] == 1 && visited[6 * m + 1] == 1 && visited[6 * m + 2] == 1 && visited[6 * m + 3] == 1 && visited[6 * m + 4] == 1 && visited[6 * m + 5] == 1){ | |
line++; break; | |
} | |
} | |
attack += 1 + 0.25 * (conne - 3); | |
} | |
} | |
} | |
}while(i < 5 || j < 6); | |
//攻撃色以外のvanishを求める | |
vanish_drop(board_copy, vanish, 0); | |
//消えるドロップがあればflag=1 | |
for(i = 0; i < 5; i++){ | |
for(j = 0; j < 6; j++){ | |
if(vanish[i][j] == 1){ | |
flag = 1; | |
} | |
} | |
} | |
//vanishの隣接行列adを求める | |
adjoin(vanish, ad); | |
//消える攻撃色以外のドロップの個数を求める。 | |
do{ | |
//vanishが1の場所を探す | |
for(i = 0; i < 5; i++){ | |
for(j = 0; j < 6; j++){ | |
if(vanish[i][j] == 1){ | |
combo++; | |
//visitedを初期化 | |
for(k = 0; k < 30; k++){ | |
visited[k] = 0; | |
} | |
//board[i][j]と一緒に消えるドロップの個数を求める | |
conne = connect(board_copy, vanish, ad, visited, 6 * i + j); | |
// printf("%d\n", conne); | |
/* for(m = 0; m < 5; m++){ | |
for(n = 0; n < 6; n++){ | |
if(vanish[m][n] == 1) printf("1"); | |
else printf("0"); | |
} | |
puts(""); | |
} | |
*/ | |
} | |
} | |
} | |
}while(i < 5 || j < 6); | |
}while(flag > 0); | |
drop(board_copy); | |
flag = 0; | |
vanish_drop(board_copy, vanish, 1); | |
for(i = 0; i < 5; i++){ | |
for(j = 0; j < 6; j++){ | |
if(vanish[i][j] == 1){ | |
flag = 1; | |
break; | |
} | |
} | |
} | |
vanish_drop(board_copy, vanish, 0); | |
for(i = 0; i < 5; i++){ | |
for(j = 0; j < 6; j++){ | |
if(vanish[i][j] == 1){ | |
flag = 1; | |
break; | |
} | |
} | |
} | |
}while(flag > 0); | |
attack *= (1 + 0.25 * (combo - 1)) * (1 + line * 0.1 * Line_Skill); | |
return attack; | |
} | |
inline void dfs(int OneSum,int num,int loc[30]){ | |
int i,j; | |
if( num==DROP_SUM ){ | |
//***メイン処理部分************************************************* | |
int board[5][6]; | |
for(i=0;i<5;i++)for(j=0;j<6;j++) board[i][j]=loc[6*i+j]; | |
double tmp; | |
if( MaxiScore <= (tmp=solve(board)) ){ | |
MaxiScore=tmp; | |
for(i=0;i<5;i++)for(j=0;j<6;j++) AnswerBoard[i][j]=board[i][j]; | |
} | |
//**************************************************************** | |
return ; | |
} | |
if( !( Attack_Drop==OneSum + ( DROP_SUM-num ) ) ){ //「ここで'1'を置かなければ、'1'の合計がAttack_Dropに満たない」という状態でなければ、以下を実行 | |
loc[num]=0; | |
dfs( OneSum ,num+1 ,loc ); | |
} | |
if( OneSum<Attack_Drop ){ //「現在の'1'の合計がAttack_Dropより少ない」時、以下を実行 | |
loc[num]=1; | |
dfs( OneSum+1 ,num+1 ,loc ); | |
} | |
} | |
int main(){ | |
int i,j; | |
int loc[30]={}; //ドロップ配置用配列(location) | |
dfs(0,0,loc); | |
for(i=0;i<5;i++){ | |
for(j=0;j<6;j++){ | |
// printf("%lf ",AnswerBoard[i][j]); | |
printf("%d ",AnswerBoard[i][j]); | |
} | |
puts(""); | |
} | |
printf("score = %lf\n",MaxiScore); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment