人鸡狗过河问题 c++编程

#include #include

typedef struct {

int a, b, c, d; } Vector;

void Add(Vector *vector1, Vector vector2, Vector* resultVector) {

resultVector->a = (vector1->a + vector2.a) % 2; resultVector->b = (vector1->b + vector2.b) % 2; resultVector->c = (vector1->c + vector2.c) % 2; resultVector->d = (vector1->d + vector2.d) % 2; }

typedef struct myNode {

Vector* stateVector; myNode* childs[4]; myNode* parent; } Node;

void Copy(Vector* targetVector, Vector* sourceVector) {

targetVector->a = sourceVector->a; targetVector->b = sourceVector->b; targetVector->c = sourceVector->c; targetVector->d = sourceVector->d; }

bool Equal(Vector* vector1, Vector* vector2) {

return vector1->a == vector2->a && vector1->b == vector2->b && vector1->c == vector2->c && vector1->d == vector2->d; }

bool IsStateAllowed(Vector* stateVector, Vector* allowedStateVectors) {

for (int i = 0; i < 10 ; i++) {

if (Equal(stateVector, &allowedStateVectors[i])) {

return true; } }

return false; }

bool HasExistInTree(Vector* targetVector, Node* tree) {

if (Equal(targetVector, tree->stateVector)) return true; else {

for (int i = 0; i < 4 ; i++) {

if (tree->childs[i] != NULL &&

HasExistInTree(targetVector, tree->childs[i])) {

return true; } } }

return false; }

void PrintAnswer(Node* node) {

while (node != NULL) {

printf(\ node->stateVector->c, node->stateVector->d); node = node->parent; }

printf(\}

void GenerateTree(Node* p, Vector* overRiverVectors, Node* tree, Vector* endState, Vector* allowedStateVectors) {

Vector* resultVector = (Vector*)malloc(sizeof(Vector)); for (int i = 0; i < 4 ; i++) {

Add(p->stateVector, overRiverVectors[i], resultVector);

if (!HasExistInTree(resultVector, tree) &&

IsStateAllowed(resultVector, allowedStateVectors)) {

p->childs[i] = (Node*)malloc(sizeof(Node));

p->childs[i]->stateVector = (Vector*)malloc(sizeof(Vector));

Copy(p->childs[i]->stateVector, resultVector); for (int j = 0; j < 4; j++) {

p->childs[i]->childs[j] = NULL; }

p->childs[i]->parent = p; } else {

p->childs[i] = NULL; } }

free(resultVector);

for (i = 0; i < 4 ; i++) {

if (p->childs[i] != NULL) {

if(!Equal(p->childs[i]->stateVector, endState)) {

GenerateTree(p->childs[i], overRiverVectors, tree, endState, allowedStateVectors); } else {

PrintAnswer(p->childs[i]); } } } }

void FreeTree(Node* node) {

if (node != NULL) {

for (int i = 0; i < 4 ; i++) {

FreeTree(node->childs[i]); }

free(node->stateVector); free(node); } }

void main() {

//渡河向量集合

Vector overRiverVectors[4] = {{1, 0, 0, 0}, {1, 1, 0, 0}, {1, 0, 1, 0}, {1, 0, 0, 1}};

//允许向量集合

Vector allowedStateVectors[10]=

{{1, 1, 1, 1}, {1, 1, 1, 0}, {1, 1, 0, 1}, {1, 0, 1, 1}, {1, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 0, 1}, {0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}};

Vector* initialState = (Vector*)malloc(sizeof(Vector)); initialState->a = 1; initialState->b = 1; initialState->c = 1; initialState->d = 1;

Vector* endState = (Vector*)malloc(sizeof(Vector)); endState->a = 0; endState->b = 0; endState->c = 0; endState->d = 0;

Node* p = (Node*)malloc(sizeof(Node));

Vector* stateVector = (Vector*)malloc(sizeof(Vector)); Copy(stateVector, initialState); p->stateVector = stateVector; for (int i = 0; i < 4 ; i++) {

p->childs[i] = NULL; }

p->parent = NULL;

GenerateTree(p, overRiverVectors, p, endState, allowedStateVectors);

FreeTree(p); free(initialState); free(endState); }

本文来源：https://www.bwwdw.com/article/j035.html