经典算法:深度优先遍历(北京大学上机题)
int arr[25];
int num;
bool isused[30];
bool DFS(int curside, int curlength, int position ,int side)
//curside 表示已经拼好的边长
//curlength 表示正在拼的边长长度
//position 木棍遍历的起点
{
if (curside == 3) { //已经三边拼好
return true;
}
for (int i = position; i < num; ++i) {
if (isused[i] == true ||curlength + arr[i] >side) //表示该木棍暂时可用
{
continue;
}
isused[i] = true; //暂时拿走木棍
if (curlength + arr[i] < side) {
if (DFS(curside, curlength + arr[i], i + 1, side) == true) {
return true; // 说明我的邻居结点满足条件
}
}
else if (curlength + arr[i] == side) {
if (DFS(curside + 1, 0, 0, side) == true) {
return true;
}
}
//取回刚才的木棍
isused[i] = false;
}
return false;
}
if (DFS(0, 0, 0, board) == true)
int num;
bool isused[30];
bool DFS(int curside, int curlength, int position ,int side)
//curside 表示已经拼好的边长
//curlength 表示正在拼的边长长度
//position 木棍遍历的起点
{
if (curside == 3) { //已经三边拼好
return true;
}
for (int i = position; i < num; ++i) {
if (isused[i] == true ||curlength + arr[i] >side) //表示该木棍暂时可用
{
continue;
}
isused[i] = true; //暂时拿走木棍
if (curlength + arr[i] < side) {
if (DFS(curside, curlength + arr[i], i + 1, side) == true) {
return true; // 说明我的邻居结点满足条件
}
}
else if (curlength + arr[i] == side) {
if (DFS(curside + 1, 0, 0, side) == true) {
return true;
}
}
//取回刚才的木棍
isused[i] = false;
}
return false;
}
if (DFS(0, 0, 0, board) == true)
全部评论
相关推荐