Տրված է միաչափ զանգված, որի տարրերը կարող են լինել 0 կամ 1։ Ընդ որում առաջին տարրը միշտ 0 - է։ Զանգվածը կարելի է շրջանցել, անցնելով միայն 0-ների վրայով, ընդ որում մեկ քայլի երկարությունն է 3 կամ 5 (3 կամ 5 տարր)։ Անհրաժեշտ է գրել ալգորիթմ, որը կստուգի տվյալ զանգվածում առաջին տարրից մինչև վերջին տարր ընկած ճանապարհի առկայությունը։ Պահանջվող ալգոր…

Is path exist

#include <iostream>
#include <queue>
#include <stdlib.h>

struct node
{
	struct node* left;
	struct node* rigth;
	int data;
};

struct node* new_node(int d)
{
	struct node* n = (struct node*) malloc(sizeof(struct node));
	n->data = d;
	n->left = 0;
	n->rigth = 0;
	return n;
}

struct node* array_to_bt(int* a, int l)
{
	std::queue<struct node*> q;
	struct node* n = new_node(0);
	struct node* r = n;
	if(a[0] != 0 || a[l - 1] != 0)
	{
		return 0;
	}
	else
	{
		if(a[3] != 0 && a[5] != 0)
		{
			return 0;
		}
		if(a[3] == 0)
		{
			n->left = new_node(3);
			q.push(n->left);
		}
		if(a[5] == 0)
		{
			n->rigth = new_node(5);
			q.push(n->rigth);
		}
	}
	while(q.size() != 0)
	{
		n = q.front();
		q.pop();
		if(a[n->data + 3] == 0 && n->data + 3 < l)
		{
			n->left = new_node(n->data + 3);
			q.push(n->left);
		}
		if(a[n->data + 5] == 0 && n->data + 5 < l)
		{
			n->rigth = new_node(n->data + 5);
			q.push(n->rigth);
		}
		if(a[n->data + 3 ] != 0 && a[n->data + 5] != 0)
		{		
		    continue;
		}
	}
	return r;
}

bool check_path(struct node* n, int d)
{
	if(n == 0)
	{
		return false;
	}
	if(d == n->data)
	{
		return true;
	}
	return check_path(n->left, d) || check_path(n->rigth, d);
}

int main()
{
	int a[] = {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0};
	int l = sizeof(a)/sizeof(a[0]);
	struct node* r = array_to_bt(a, l);
	bool b = check_path(r, l - 1);
	if(d != 0)
	{
		std::cout << "Path exist" << std::endl;
	}
	else
	{
		std::cout << "Path does not exist" << std::endl;
	}
        return 0;
}