problem_2_16

#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <string.h>
#include <queue>
using namespace std;
struct que
{
	int x;//点的编号
	int n;//第几个点
	int trace[20];//当前手势路径
}now;
struct que nex;
queue<que> q;
struct p  //记录每个点坐标
{
	int x;//横坐标
	int y;//纵坐标
}Point[20];//将每个点标号
int mid[20][20][2];       //记录两个点连线之间会有哪些点
int main()
{
	int i, j, k, num = 0, con = 0, res = 0 ,flag;
	for (i = 1; i <= 4; i++)  //将每个点标号
	{
		for (j = 1; j <= 4; j++)
		{
			Point[++num].x = i;
			Point[num].y = j;
		}
	}

	memset(mid, -1, sizeof(mid));
	for (i = 1; i <= 15; i++)
	{
		for (j = i + 1; j <= 16; j++)
		{
			con = 0;
			for (num = i + 1; num < j; num++)
			{
				if ((Point[num].x - Point[i].x)*(Point[j].y - Point[num].y) == (Point[j].x - Point[num].x)*(Point[num].y - Point[i].y))
				{
					mid[i][j][con] = num; 
					mid[j][i][con++] = num;
				}
			}
		}
	}

	for (i = 1; i <= 16; i++)
	{
		while (!q.empty())
		{
			q.pop();
		}
		nex.n = 1;
		nex.x = i;
		memset(nex.trace, 0, sizeof(nex.trace));
		nex.trace[nex.n] = i;
		q.push(nex);
		while (!q.empty())
		{
			now = q.front();
			if (now.n >= 4)
			{
				res++;         //手势数加一
				//for (int h = 1; h <= now.n; h++)
				//{
				//	printf("%d->", now.trace[h]);
				//}
				//printf("\n");
			}
			for (j = 1; j <= 16; j++)
			{
				flag = 0;
				for (k = 1; k <= now.n; k++)
				{
					if (now.trace[k] == j)
					{
						flag = 1;
						break;
					}
				}
				if (flag == 1)
					continue;
				if (mid[now.x][j][0] == -1 && mid[now.x][j][1] == -1)   //两点之间是否有未连接的其他点
				{
					nex.n = now.n + 1;
					nex.x = j;
					for (k = 1; k <= now.n; k++)
						nex.trace[k] = now.trace[k];
					nex.trace[nex.n] = j;
					q.push(nex);
				}
			}
			q.pop();
		}
	}


	printf("%d\n", res);
	return 0;
}