本文最后更新于 1163 天前,其中的信息可能已经有所发展或是发生改变。
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int a[100];
int vis[4][5]; //下标为0的不用
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int result = 0;
struct node
{
int x, y;
}s;
void bfs(int a[])
{
memset(vis, 0, sizeof(vis)); //记得将vis置零,防止有残余的1
int x, y;
//把一维下标转换为二维坐标
for (int i = 1; i <= 5; ++i)
{
if (a[i] % 4 == 0)
{
x = a[i] / 4;
y = 4;
}
else
{
x = a[i] / 4 + 1;
y = a[i] % 4;
}
vis[x][y] = 1;
}
s.x = x;
s.y = y;
queue<node>Q;
Q.push(s);
vis[s.x][s.y] = 0;
int num = 1;
node t;
while (!Q.empty())
{
t = Q.front();
Q.pop();
for (int i = 0; i < 4; ++i)
{
int xx = t.x + dx[i];
int yy = t.y + dy[i];
if (xx >= 1 && xx <= 3 && yy >= 1 && yy <= 4 && vis[xx][yy] == 1)
{
++num; //每有一个相连,num就自增
vis[xx][yy] = 0;
s.x = xx;
s.y = yy;
Q.push(s);
}
}
}
if (num == 5) //如果这5个数都相连
{
++result;
}
}
void dfs(int step) //从12个数中取出5个(即12取5的所有组合),存入一维数组a中(从下标1开始存储)
{
if (step == 6)
{
bfs(a); //用bfs判断取出的这5个数在图中是否相连
return;
}
for (int i = 1; i <= 12; ++i)
{
if (i > a[step - 1]) //以递增的顺序选出,可以防止重复
{
a[step] = i;
dfs(step + 1);
}
}
}
int main()
{
memset(a, 0, sizeof(a));
dfs(1);
cout << result << endl;
return 0;
}
Post Views: 193