Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
blue_lotus test problem 2
#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 <= 3; i++) //将每个点标号
{
for (j = 1; j <= 3; j++)
{
Point[++num].x = i;
Point[num].y = j;
}
}
memset(mid, -1, sizeof(mid));
for (i = 1; i <= 8; i++)
{
for (j = i + 1; j <= 9; 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 <= 9; 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 <= 9; 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment