/*************************************************************************************
18. 在一線性七個格位置的圖上有兩種不同顏色的棋子Ａ，Ｂ. 排列如下圖所示，中間
 格的位置為空。

          ┎─┰─┰─┰─┰─┰─┰─┒
          ┃Ａ┃Ａ┃Ａ┃  ┃Ｂ┃Ｂ┃Ｂ┃
          ┖─┸─┸─┸─┸─┸─┸─┚

 要求將Ａ，Ｂ的現行位置交換,形成下圖中的排列：

          ┎─┰─┰─┰─┰─┰─┰─┒
          ┃Ｂ┃Ｂ┃Ｂ┃  ┃Ａ┃Ａ┃Ａ┃
          ┖─┸─┸─┸─┸─┸─┸─┚

 移動棋子的條件：

   (1) 每個格中只準放一個棋子。
   (2) 任意一個棋子均可移動一格放入空格內。
   (3) 一方的棋子均可跳過另一方的一個棋子進入空格。
   (4) 任何棋子不得跳躍兩個或兩個以上棋子（無論顏色同異）
   (5) 任何一個顏色棋子只能向前跳，不準向后跳。

 編程完成有關的移動，并且完成具有２Ｎ＋１個格子的情形. 其中兩種顏色各有
 Ｎ個棋子,且中間為空格.

  分析: 列出最簡單的幾種(如N=3,N=5,N=7)的走法,總結規律
**************************************************************************************/

#include <stdio.h>
#include <malloc.h>

int count = 0;

//flag = 1,空格向右移動,否則向左移動
void move(char* chesses, int* ppos, int flag)
{
	if(flag)
	{ 
		chesses[*ppos] = chesses[*ppos+1];
		chesses[*ppos+1] = ' ';
		*ppos = *ppos+1;
	}
	else
	{
		chesses[*ppos] = chesses[*ppos-1];
		chesses[*ppos-1] = ' ';
		*ppos = *ppos-1;
	}
	count ++;
}

//flag = 1,空格向右跳,否則向左跳
void jump(char* chesses, int* ppos, int flag)
{
	
	if(flag)
	{ 
		chesses[*ppos] = chesses[*ppos+2];
		chesses[*ppos+2] = ' ';
		*ppos = *ppos + 2;
	}
	else
	{
		chesses[*ppos] = chesses[*ppos-2];
		chesses[*ppos-2] = ' ';
		*ppos = *ppos - 2;
	}
	count ++;
}

//顯示棋子狀態
void print_chesses(char* chesses,int size)
{
	int i;
	for(i=0; i<size; i++)
		printf("%c",chesses[i]);
	printf("\n");
}

void main()
{
	
	int n;
	int N;
	int pos;
	char* chesses;
	int count_jmp = 1;
	int move_dirt = 0;
	int jump_dirt = 1;
	int dc = 1;//計數遞增方向,取-1和-1


	printf("請輸入一個正整數n: ");
	scanf("%d", &n);

	N = 2*n + 1;
	pos = n;
	chesses = (char*)malloc(N*sizeof(char));

	{
		int i;
		for(i=0; i<n; i++)
			chesses[i] = 'A';
		chesses[i++] = ' ';
		for(;i<N; i++)
			chesses[i] = 'B';
		print_chesses(chesses,N);
	}

	while(count_jmp!=0)
	{
		int i;

		move(chesses, &pos, move_dirt);
		print_chesses(chesses,N);

		for(i=0; i<count_jmp; i++)
		{
			jump(chesses,&pos,jump_dirt);
			print_chesses(chesses,N);
		}
		jump_dirt = !jump_dirt;
		if(count_jmp == n)
		{
			dc = -dc;
		}
		else move_dirt = !move_dirt;;
		count_jmp += dc;
	}
	move(chesses, &pos, move_dirt);
	print_chesses(chesses,N);

	printf("%d\n",count+1);

	free(chesses);
}