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