#include <stdio.h>
#include <Windows.h>
#include <time.h>


#define SIZE 16
#define ARRAY 10000000

const int md0[] = { 6, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6 };
const int md1[] = { 5, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5 };
const int md2[] = { 4, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4 };
const int md3[] = { 3, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3 };

const int md4[] = { 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5 };
const int md5[] = { 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4 };
const int md6[] = { 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3 };
const int md7[] = { 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2 };

const int md8[] = { 4, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4 };
const int md9[] = { 3, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3 };
const int md10[] = { 2, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2 };
const int md11[] = { 1, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1 };

const int md12[] = { 3, 3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3 };
const int md13[] = { 2, 4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2 };
const int md14[] = { 1, 5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1 };
const int md15[] = { 0, 6, 5, 4, 3, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0 };

const int up[] = { -1, -1, -1,-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
const int down[] = { 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, };
const int left[] = { -1, 0, 1, 2, -1, 4, 5, 6, -1, 8, 9, 10, -1, 12, 13, 14 };
const int right[] = { 1, 2, 3, -1, 5, 6, 7, -1, 9, 10, 11, -1, 13, 14, 15, -1 };


typedef struct heap {
	int ban[SIZE];
	int cost;
	int moves;
	struct heap *parent;
} HEAP;

void printban(int* ban) {

	int i;

	for (i = 0; i<SIZE; i++) {
		printf("%d ", ban[i]);
		if (i == 3 || i == 7 || i == 11 || i == 15) { printf("\n"); }
	}
	printf("\n");
}

void inputban(int* ban) {

	int 	k = 2;

	COORD coord;
	coord.X = 0;
	coord.Y = 4;

	for (int i = 0; i<SIZE; i++) {

		scanf_s("%d", &ban[i]);
		getchar();

		if (i == 3 || i == 7 || i == 11 || i == 15) {

			coord.Y = coord.Y + 1;
			coord.X = 0;

			SetConsoleCursorPosition(
				GetStdHandle(STD_OUTPUT_HANDLE),
				coord);

			k = 2;

		}
		else {

			coord.X = k;

			SetConsoleCursorPosition(
				GetStdHandle(STD_OUTPUT_HANDLE),
				coord);

			k = k + 2;

		}
	}

	printf("\n\n");

}



void add_heap2(HEAP *heap, int last, int *ban, int cost, int moves, HEAP *parent) {

	for (int i = 0; i < SIZE; i++) {

		(heap + last)->ban[i] = ban[i];
	}
	(heap + last)->moves = moves;
	(heap + last)->cost = cost;
	(heap + last)->parent = parent;

}
HEAP* add_node(HEAP *temp, HEAP *close, int last) {



	for (int i = 0; i < SIZE; i++) {

		(close + last)->ban[i] = temp->ban[i];

	}

	(close + last)->parent = temp->parent;
	(close + last)->moves = temp->moves;
	(close + last)->cost = temp->cost;

	return (close + last);

}

int distance(int *ban) {

	int cost = 0;

	cost = cost + md0[ban[0]];
	cost = cost + md1[ban[1]];
	cost = cost + md2[ban[2]];
	cost = cost + md3[ban[3]];
	cost = cost + md4[ban[4]];
	cost = cost + md5[ban[5]];
	cost = cost + md6[ban[6]];
	cost = cost + md7[ban[7]];
	cost = cost + md8[ban[8]];
	cost = cost + md9[ban[9]];
	cost = cost + md10[ban[10]];
	cost = cost + md11[ban[11]];
	cost = cost + md12[ban[12]];
	cost = cost + md13[ban[13]];
	cost = cost + md14[ban[14]];
	cost = cost + md15[ban[15]];

	return cost;

}


int checkGoal(int *ban) {

	return ban[0] == 1 && ban[1] == 2 && ban[2] == 3 && ban[3] == 4 && ban[4] == 5 && ban[5] == 6 && ban[6] == 7 && ban[7] == 8 &&
		ban[8] == 9 && ban[9] == 10 && ban[10] == 11 && ban[11] == 12 && ban[12] == 13 && ban[13] == 14 && ban[14] == 15 && ban[15] == 0;

}

int searchzero(int *ban) {

	int j;

	for (int i = 0; i < SIZE; i++) {

		if (ban[i] == 0) {

			j = i;

		}

	}

	return j;//0の位置を返す

}

void up_sort(HEAP *heap, int watch) {//

	HEAP *temp = NULL;

	if (temp == NULL) {

		if ((temp = malloc(sizeof(HEAP))) == NULL) {
			fprintf(stderr, "メモリーエラー\n");
			exit(1);
		}
	}

	int parent;

	parent = (watch - 1) / 2;


	//子が親以下のとき
	while ((heap + parent)->cost >= (heap + watch)->cost) {

		//子が親と等しいとき
		if ((heap + parent)->cost == (heap + watch)->cost) {


			//子が親と等しく、かつ実コストが親より小さいとき
			if ((heap + parent)->moves > (heap + watch)->moves) {

				*temp = *(heap + parent);

				*(heap + parent) = *(heap + watch);
				*(heap + watch) = *temp;

				if (parent == 0) {

					break;

				}
				else {

					watch = parent;
					parent = (watch - 1) / 2;

				}

			}
			else {

				break;

			}

		}
		else {

			//入れ替え

			*temp = *(heap + parent);

			*(heap + parent) = *(heap + watch);
			*(heap + watch) = *temp;

			if (parent == 0) {

				break;

			}
			else {

				watch = parent;
				parent = (watch - 1) / 2;

			}

		}
	}
}

void down_sort(HEAP *heap, int last) {//

	int parent = 0;
	HEAP *temp = NULL;

	if (temp == NULL) {

		if ((temp = malloc(sizeof(HEAP))) == NULL) {
			fprintf(stderr, "メモリーエラー\n");
			exit(1);
		}
	}

	while (last >= (2 * parent) + 1 || last >= (2 * parent) + 2) {//lastが子以上のとき繰り返す


		if ((heap + (2 * parent) + 1)->cost == (heap + (2 * parent) + 2)->cost) {//子が等しいとき


			if ((heap + (2 * parent) + 1)->moves < (heap + (2 * parent) + 2)->moves) {//左の子の実コストが低いとき


				if ((heap + parent)->cost > (heap + (2 * parent) + 1)->cost) {//親より左の子が小さいとき

					*temp = *(heap + parent);

					*(heap + parent) = *(heap + (2 * parent) + 1);
					*(heap + (2 * parent) + 1) = *temp;

					parent = (2 * parent) + 1;


				}
				else if ((heap + parent)->cost < (heap + (2 * parent) + 1)->cost) {//親より左の子が大きいとき

					break;

				}
				else {//親と左の子が等しい



					if ((heap + parent)->moves > (heap + (2 * parent) + 1)->moves) {//子の実コスト小さい


						*temp = *(heap + parent);

						*(heap + parent) = *(heap + (2 * parent) + 1);
						*(heap + (2 * parent) + 1) = *temp;

						parent = (2 * parent) + 1;




					}
					else {//親の実コスト大きい

						break;

					}


				}

			}
			else {//右の子の実コストが低い時


				if ((heap + parent)->cost > (heap + (2 * parent) + 2)->cost) {//親より右の子が小さいとき

					*temp = *(heap + parent);

					*(heap + parent) = *(heap + (2 * parent) + 2);
					*(heap + (2 * parent) + 2) = *temp;

					parent = (2 * parent) + 2;


				}
				else if ((heap + parent)->cost < (heap + (2 * parent) + 2)->cost) {//親より右の子が大きいとき

					break;

				}
				else//親と右の子等しいとき
				{
					if ((heap + parent)->moves > (heap + (2 * parent) + 2)->moves) {//子の実コスト小さい


						*temp = *(heap + parent);
						*(heap + parent) = *(heap + (2 * parent) + 2);
						*(heap + (2 * parent) + 2) = *temp;

						parent = (2 * parent) + 2;
					}
					else {//親の実コスト大きい

						break;

					}


				}

			}
		}

		//子が等しいとき終わり
		else

			if ((heap + (2 * parent) + 1)->cost < (heap + (2 * parent) + 2)->cost) {//左の子が右の子より小さいとき


				if ((heap + parent)->cost == (heap + (2 * parent) + 1)->cost) {//親と左の子が等しいとき


					if ((heap + parent)->moves > (heap + (2 * parent) + 1)->moves) {//左の子の実コストが低いとき

						*temp = *(heap + parent);
						*(heap + parent) = *(heap + (2 * parent) + 1);
						*(heap + (2 * parent) + 1) = *temp;

						parent = (2 * parent) + 1;

					}
					else {//左の子の実コストが高いとき

						break;

					}

				}
				else if ((heap + parent)->cost > (heap + (2 * parent) + 1)->cost) {//親より左の子が小さいとき

					*temp = *(heap + parent);
					*(heap + parent) = *(heap + (2 * parent) + 1);
					*(heap + (2 * parent) + 1) = *temp;

					parent = (2 * parent) + 1;

				}
				else {//親が左の子より小さいとき

					break;

				}
			}//左終わり
			else
				if ((heap + (2 * parent) + 1)->cost > (heap + (2 * parent) + 2)->cost) {//右の子が左の子より小さいとき


					if ((heap + parent)->cost == (heap + (2 * parent) + 2)->cost) {//親と右の子が等しいとき


						if ((heap + parent)->moves > (heap + (2 * parent) + 2)->moves) {//右の子の実コストが低いとき

							*temp = *(heap + parent);
							*(heap + parent) = *(heap + (2 * parent) + 2);
							*(heap + (2 * parent) + 2) = *temp;

							parent = (2 * parent) + 2;

						}
						else {//右の子の実コストが高いとき

							break;

						}

					}
					else if ((heap + parent)->cost > (heap + (2 * parent) + 1)->cost) {//親より右の子が小さいとき

						*temp = *(heap + parent);
						*(heap + parent) = *(heap + (2 * parent) + 2);
						*(heap + (2 * parent) + 2) = *temp;

						parent = (2 * parent) + 2;

					}
					else {//親が右の子より小さいとき

						break;

					}
				}


	}
}


HEAP* minimum(HEAP *heap, int last) {

	HEAP *temp = NULL;
	if (temp == NULL) {

		if ((temp = malloc(sizeof(HEAP))) == NULL) {
			fprintf(stderr, "メモリーエラー\n");
			exit(1);
		}
	}
	//最小値を取り出す

	*temp = *heap;



	//根に要素追加
	if (last == 0) {

		heap->cost = 99;
		heap->moves = 99;
		heap->parent = NULL;

	}
	else {

		*heap = *(heap + last);

		(heap + last)->moves = 99;
		(heap + last)->cost = 99;

	}

	return temp;


}

int search(int *ban, int moves, int cost, HEAP *heap, HEAP *close, int last, int closelast) {

	for (int i = 0; i < closelast; i++) {

		if (cost == (close + i)->cost) {

			if (ban[0] == (close + i)->ban[0] && ban[1] == (close + i)->ban[1] && ban[2] == (close + i)->ban[2] &&
				ban[3] == (close + i)->ban[3] && ban[4] == (close + i)->ban[4] && ban[5] == (close + i)->ban[5] &&
				ban[6] == (close + i)->ban[6] && ban[7] == (close + i)->ban[7] && ban[8] == (close + i)->ban[8] &&
				ban[9] == (close + i)->ban[9] && ban[10] == (close + i)->ban[10] && ban[11] == (close + i)->ban[11] &&
				ban[12] == (close + i)->ban[12] && ban[13] == (close + i)->ban[13] && ban[14] == (close + i)->ban[14] &&
				ban[15] == (close + i)->ban[15]) {

				return 0;

			}
		}
	}

	for (int i = 0; i < last; i++) {

		if (cost == (heap + i)->cost) {

			if (ban[0] == (heap + i)->ban[0] && ban[1] == (heap + i)->ban[1] && ban[2] == (heap + i)->ban[2] &&
				ban[3] == (heap + i)->ban[3] && ban[4] == (heap + i)->ban[4] && ban[5] == (heap + i)->ban[5] &&
				ban[6] == (heap + i)->ban[6] && ban[7] == (heap + i)->ban[7] && ban[8] == (heap + i)->ban[8] &&
				ban[9] == (heap + i)->ban[9] && ban[10] == (heap + i)->ban[10] && ban[11] == (heap + i)->ban[11] &&
				ban[12] == (heap + i)->ban[12] && ban[13] == (heap + i)->ban[13] && ban[14] == (heap + i)->ban[14] &&
				ban[15] == (heap + i)->ban[15]) {
				return 0;
			}

		}
	}

	return 1;

}

int checkparent(int *ban, HEAP *parent) {

	if (parent->parent == NULL) { return 1; }

	if (ban[0] == parent->parent->ban[0] && ban[1] == parent->parent->ban[1] && ban[2] == parent->parent->ban[2] &&
		ban[3] == parent->parent->ban[3] && ban[4] == parent->parent->ban[4] && ban[5] == parent->parent->ban[5] &&
		ban[6] == parent->parent->ban[6] && ban[7] == parent->parent->ban[7] && ban[8] == parent->parent->ban[8] &&
		ban[9] == parent->parent->ban[9] && ban[10] == parent->parent->ban[10] && ban[11] == parent->parent->ban[11] &&
		ban[12] == parent->parent->ban[12] && ban[13] == parent->parent->ban[13] && ban[14] == parent->parent->ban[14] &&
		ban[15] == parent->parent->ban[15]) {

		return 0;

	}

	return 1;

}

int moveitem(int i, int j, int *ban, int last, int moves, HEAP *heap, HEAP *parent, HEAP *close, int closelast) {

	int temp, cost;

	//入れ替え
	temp = ban[i];
	ban[i] = ban[j];
	ban[j] = temp;

	//コスト計算
	moves++;
	cost = moves + distance(ban);

	//heapとcloseにあるか調べる
	if (search(ban, moves, cost, heap, close, last, closelast) == 1) {
		
		//ヒープへ追加
		add_heap2(heap, last, ban, cost, moves, parent);

		//ヒープ並び替え
		up_sort(heap, last);

		//入れ替えた数字を元に戻す
		ban[j] = ban[i];
		ban[i] = temp;

		last++;
	}

	return last;//ヒープの最後

}

int move(int *ban, int last, int moves, HEAP *heap, HEAP *parent, HEAP *close, int closelast) {

	int j;

	//0の位置を探す
	j = searchzero(ban);


	//盤面入れ替え

	if (parent->parent == NULL) {

		if (up[j] != -1) { last = moveitem(j, up[j], ban, last, moves, heap, parent, close, closelast); }
		if (down[j] != -1) { last = moveitem(j, down[j], ban, last, moves, heap, parent, close, closelast); }
		if (left[j] != -1) { last = moveitem(j, left[j], ban, last, moves, heap, parent, close, closelast); }
		if (right[j] != -1) { last = moveitem(j, right[j], ban, last, moves, heap, parent, close, closelast); }
		return last;



	}
	else {



		if (up[j] != -1 && parent->parent->ban[up[j]] != 0) { last = moveitem(j, up[j], ban, last, moves, heap, parent, close, closelast); }
		if (down[j] != -1 && parent->parent->ban[down[j]] != 0) { last = moveitem(j, down[j], ban, last, moves, heap, parent, close, closelast); }
		if (left[j] != -1 && parent->parent->ban[left[j]] != 0) { last = moveitem(j, left[j], ban, last, moves, heap, parent, close, closelast); }
		if (right[j] != -1 && parent->parent->ban[right[j]] != 0) { last = moveitem(j, right[j], ban, last, moves, heap, parent, close, closelast); }
		return last;

	}
}

void initialize(HEAP *heap) {


	for (int i = 0; i < ARRAY; i++) {

		(heap + i)->moves = 99;
		(heap + i)->cost = 99;


	}



}

void print(HEAP *node) {

	if (node->parent == NULL) {

		printban(node->ban);
		printf("moves：%d\n", node->moves);

	}
	else {


		print(node->parent);
		printban(node->ban);
		printf("moves：%d\n", node->moves);

	}

}

void ran(int *ban) {

	int i, j, k;
	int l = 100;//ランダムに移動する回数

	unsigned int ti;




	ti = (unsigned int)time(0);
	srand(ti);

	while (l > 0) {

		for (i = 0; i < 16; i++) {

			if (ban[i] == 0) { j = i; }

		}




		switch (j) {

		case 0:

			k = (rand() % 2);

			if (k == 1) {

				ban[0] = ban[1];
				ban[1] = 0;

			}
			else {

				ban[0] = ban[4];
				ban[4] = 0;

			}

			break;

		case 1:

			k = (rand() % 3);

			if (k == 0) {

				ban[1] = ban[0];
				ban[0] = 0;

			}
			else if (k == 1) {

				ban[1] = ban[5];
				ban[5] = 0;

			}
			else {

				ban[1] = ban[2];
				ban[2] = 0;

			}

			break;

		case 2:

			k = (rand() % 3);

			if (k == 0) {

				ban[2] = ban[1];
				ban[1] = 0;

			}
			else if (k == 1) {

				ban[2] = ban[6];
				ban[6] = 0;

			}
			else {

				ban[2] = ban[3];
				ban[3] = 0;

			}

			break;

		case 3:

			k = (rand() % 2);

			if (k == 1) {

				ban[3] = ban[2];
				ban[2] = 0;

			}
			else {

				ban[3] = ban[7];
				ban[7] = 0;

			}

			break;

		case 4:

			k = (rand() % 3);

			if (k == 0) {

				ban[4] = ban[0];
				ban[0] = 0;

			}
			else if (k == 1) {

				ban[4] = ban[5];
				ban[5] = 0;

			}
			else {

				ban[4] = ban[8];
				ban[8] = 0;

			}

			break;

		case 5:

			k = (rand() % 4);

			if (k == 0) {

				ban[5] = ban[1];
				ban[1] = 0;

			}
			else if (k == 1) {

				ban[5] = ban[4];
				ban[4] = 0;

			}
			else if (k == 2) {

				ban[5] = ban[9];
				ban[9] = 0;

			}
			else {

				ban[5] = ban[6];
				ban[6] = 0;


			}

			break;

		case 6:

			k = (rand() % 4);

			if (k == 0) {

				ban[6] = ban[2];
				ban[2] = 0;

			}
			else if (k == 1) {

				ban[6] = ban[5];
				ban[5] = 0;

			}
			else if (k == 2) {

				ban[6] = ban[10];
				ban[10] = 0;

			}
			else {

				ban[6] = ban[7];
				ban[7] = 0;


			}

			break;

		case 7:

			k = (rand() % 3);

			if (k == 0) {

				ban[7] = ban[3];
				ban[3] = 0;

			}
			else if (k == 1) {

				ban[7] = ban[6];
				ban[6] = 0;

			}
			else {

				ban[7] = ban[11];
				ban[11] = 0;

			}

			break;

		case 8:

			k = (rand() % 3);

			if (k == 0) {

				ban[8] = ban[4];
				ban[4] = 0;

			}
			else if (k == 1) {

				ban[8] = ban[12];
				ban[12] = 0;

			}
			else {

				ban[8] = ban[9];
				ban[9] = 0;

			}

			break;

		case 9:

			k = (rand() % 4);

			if (k == 0) {

				ban[9] = ban[5];
				ban[5] = 0;

			}
			else if (k == 1) {

				ban[9] = ban[8];
				ban[8] = 0;

			}
			else if (k == 2) {

				ban[9] = ban[13];
				ban[13] = 0;

			}
			else {

				ban[9] = ban[10];
				ban[10] = 0;


			}

			break;

		case 10:

			k = (rand() % 4);

			if (k == 0) {

				ban[10] = ban[6];
				ban[6] = 0;

			}
			else if (k == 1) {

				ban[10] = ban[9];
				ban[9] = 0;

			}
			else if (k == 2) {

				ban[10] = ban[14];
				ban[14] = 0;

			}
			else {

				ban[10] = ban[11];
				ban[11] = 0;


			}

			break;

		case 11:

			k = (rand() % 3);

			if (k == 0) {

				ban[11] = ban[7];
				ban[7] = 0;

			}
			else if (k == 1) {

				ban[11] = ban[10];
				ban[10] = 0;

			}
			else {

				ban[11] = ban[15];
				ban[15] = 0;

			}

			break;




		case 12:

			k = (rand() % 2);

			if (k == 1) {

				ban[12] = ban[8];
				ban[8] = 0;

			}
			else {

				ban[12] = ban[13];
				ban[13] = 0;

			}


			break;

		case 13:

			k = (rand() % 3);

			if (k == 0) {

				ban[13] = ban[12];
				ban[12] = 0;

			}
			else if (k == 1) {

				ban[13] = ban[9];
				ban[9] = 0;

			}
			else {

				ban[13] = ban[14];
				ban[14] = 0;

			}

			break;

		case 14:

			k = (rand() % 3);

			if (k == 0) {

				ban[14] = ban[13];
				ban[13] = 0;

			}
			else if (k == 1) {

				ban[14] = ban[10];
				ban[10] = 0;

			}
			else {

				ban[14] = ban[15];
				ban[15] = 0;

			}

			break;

		case 15:

			k = (rand() % 2);

			if (k == 1) {

				ban[15] = ban[11];
				ban[11] = 0;

			}
			else {

				ban[15] = ban[14];
				ban[14] = 0;

			}

			break;


		}

		l--;

	}

}


int main(void) {

	int last = 0;//ヒープのラスト
	int closelast = 0;//closeのラスト
	int moves = 0;//移動回数
	int cost;
	int ban[SIZE]; //初期盤面
	int d;


	HEAP *heap = NULL;
	if (heap == NULL) {

		if ((heap = malloc(ARRAY*sizeof(HEAP))) == NULL) {

			fprintf(stderr, "メモリーエラー\n");
			exit(1);

		}
	}

	HEAP *close = NULL;
	if (close == NULL) {

		if ((close = malloc(3000000 * sizeof(HEAP))) == NULL) {

			fprintf(stderr, "メモリーエラー\n");
			exit(1);

		}
	}



	HEAP *temp = NULL;
	if (temp == NULL) {

		if ((temp = malloc(sizeof(HEAP))) == NULL) {
			fprintf(stderr, "メモリーエラー\n");
			exit(1);
		}
	}


	


	printf("ランダム:1　固定:2\n");

	scanf_s("%d", &d);
	

	if (d == 1) {

		ban[0] = 1;
		ban[1] = 2;
		ban[2] = 3;
		ban[3] = 4;
		ban[4] = 5;
		ban[5] = 6;
		ban[6] = 7;
		ban[7] = 8;
		ban[8] = 9;
		ban[9] = 10;
		ban[10] = 11;
		ban[11] = 12;
		ban[12] = 13;
		ban[13] = 14;
		ban[14] = 15;
		ban[15] = 0;



		ran(ban);

	}
	else {//固定

		


		ban[0] = 1;//14
		ban[1] = 2;
		ban[2] = 4;
		ban[3] = 8;
		ban[4] = 5;
		ban[5] = 6;
		ban[6] = 3;
		ban[7] = 12;
		ban[8] = 13;
		ban[9] = 9;
		ban[10] = 7;
		ban[11] = 15;
		ban[12] = 10;
		ban[13] = 14;
		ban[14] = 11;
		ban[15] = 0;








	}


	initialize(heap);

	printban(ban);

	cost = distance(ban);


	

	for (int i = 0; i < SIZE; i++) {

		temp->ban[i] = ban[i];

	}

	temp->cost = cost;
	temp->moves = 0;
	temp->parent = NULL;

	

	//時間計測
	clock_t start, end;
	start = clock();

	while (checkGoal(temp->ban) != 1) {//ゴールかチェック


		temp->parent = add_node(temp, close, closelast);//closeへ移動し親のアドレス受け取る
		closelast++;

		//隣接ノード生成、コスト計算、ヒープへ追加
		last = move(temp->ban, last, temp->moves, heap, temp->parent, close, closelast);


		//最小値を取り出す
		last--;
		temp = minimum(heap, last);

		
		//ヒープ組直し
		down_sort(heap, last);


	}

	end = clock();

	printf("計算時間：%.2f秒\n", (double)(end - start) / CLOCKS_PER_SEC);



	printf("最短経路表示\n");
	print(temp);
	printf("最短手数：%d\n", temp->moves);

	return 0;

}