breadthfirst.cpp

人工智能中重要的一个问题, 用广度优先搜索的方法解决

// breadthfirst.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#include <queue>
using namespace std; 
struct oil{
	int e;
	int s;
	int parent;
	int self;
	int sign;
	oil()
	{
		e=0;
		s=0;
		parent=0;
		self=0;
		sign=0;
	};
	
};
void main()
{
	int i=0;
	int j=0;
	int same=0;
	int h=0;
	queue <oil> oilqueue;
	oil oilarray[40];
    oil array[20];
	oil node;
	oil node1;
	oil node2;
	oil topnode;
	for(j=0;j<40;j++)
	{
		oilarray[j]=node;
	}
	oilqueue.push(node);
	
	while(!node2.sign&&!(oilqueue.size()<1))
	{
		topnode=oilqueue.front();
		oilqueue.pop();
		node1=topnode;
		
		if(node1.e<7)
		{
			node1.e=7;
			
			for(j=0;j<=i;j++)
			{
				if((node1.e==oilarray[j].e)&&(node1.s==oilarray[j].s))
					same=1;
			}
			
			
			if(same==1)
			{
				node1=topnode;
				same=0;
			}
			else
			{
				i++;
				
				oilarray[i]=node1;
				oilarray[i].self=i;
				oilarray[i].parent=topnode.self;
				oilqueue.push(oilarray[i]);
				node2=oilarray[i];
				node1=topnode;
				
			}
			
			if(node2.e==5)
			{
				
				array[i]=oilarray[i];
				for(j=i;j>0&&array[j].parent!=0;j--)
				{
					array[j-1]=oilarray[array[j].parent];
				}
				
				node2.sign=1;
				
			}
			
			
        }
		
		
		if(node1.s<3)
		{
			
			node1.s=3;
			
			
			for(j=0;j<=i;j++)
			{
				if((node1.e==oilarray[j].e)&&(node1.s==oilarray[j].s))
					same=1;
			}
			if(same==1)
			{
				node1=topnode;
				same=0;
			}
			else
			{
				i++;
				
				oilarray[i]=node1;
				oilarray[i].self=i;
				oilarray[i].parent=topnode.self;
				oilqueue.push(oilarray[i]);
				node2=oilarray[i];
				node1=topnode;
				
			}
			
			if(node2.e==5)
			{
				
				array[i]=oilarray[i];
				
				for(j=i;j>0&&array[j].parent!=0;j--)
				{	
					array[j-1]=oilarray[array[j].parent];
				}
				
				node2.sign=1;
				
			}
			
			
		}

		if(node1.e>0)
		{
			node1.e=0;
			
			for(j=0;j<=i;j++)
			{
				if((node1.e==oilarray[j].e)&&(node1.s==oilarray[j].s))
					same=1;
			}
			if(same==1)
			{
				node1=topnode;
				same=0;
			}
			else
			{
				i++;
				
				oilarray[i]=node1;
				oilarray[i].self=i;
				oilarray[i].parent=topnode.self;
				oilqueue.push(oilarray[i]);
				node2=oilarray[i];
				node1=topnode;
				
			}
			
			if(node2.e==5)
			{
				
				array[i]=node2;
				for(j=i;j>0&&array[j].parent!=0;j--)
				{	
					array[j-1]=oilarray[array[j].parent];
				}
				
				node2.sign=1;
				
			}
			
			
		}
		
		if(node1.s>0)
		{
			node1.s=0;
			
			
			for(j=0;j<=i;j++)
			{
				if((node1.e==oilarray[j].e)&&(node1.s==oilarray[j].s))
					same=1;
			}
			if(same==1)
			{
				node1=topnode;
				same=0;
			}
			else
			{
				i++;
				
				oilarray[i]=node1;
				oilarray[i].self=i;
				oilarray[i].parent=topnode.self;
				oilqueue.push(oilarray[i]);
				node2=oilarray[i];
				node1=topnode;
				
			}
			
			if(node2.e==5)
			{
				
				array[i]=node2;
				for(j=i;j>0&&array[j].parent!=0;j--)
				{	
					array[j-1]=oilarray[array[j].parent];
				}
				
				node2.sign=1;
				
			}
			
			
		}
		
		if(node1.e>0&&(node1.e+node1.s<=3))
		{
			node1.s=node1.e+node1.s;
			node1.e=0;
			
			
			for(j=0;j<=i;j++)
			{
				if((node1.e==oilarray[j].e)&&(node1.s==oilarray[j].s))
					same=1;
			}
			if(same==1)
			{
				node1=topnode;
				same=0;
			}
			else
			{
				i++;
				
				oilarray[i]=node1;
				oilarray[i].self=i;
				oilarray[i].parent=topnode.self;
				oilqueue.push(oilarray[i]);
				node2=oilarray[i];
				node1=topnode;
				
			}
			
			if(node2.e==5)
			{
				
				array[i]=node2;
				for(j=i;j>0&&array[j].parent!=0;j--)
				{	
					array[j-1]=oilarray[array[j].parent];
				}
				
				node2.sign=1;
				
			}
			
			
		}

		if(node1.s>0&&(node1.e+node1.s<=7))
		{
			node1.e=node1.e+node1.s;
			node1.s=0;
			
			for(j=0;j<=i;j++)
			{
				if((node1.e==oilarray[j].e)&&(node1.s==oilarray[j].s))
					same=1;
			}
			if(same==1)
			{
				node1=topnode;
				same=0;
			}
			else
			{
				i++;
				
				oilarray[i]=node1;
				oilarray[i].self=i;
				oilarray[i].parent=topnode.self;
				oilqueue.push(oilarray[i]);
				node2=oilarray[i];
				node1=topnode;
				
			}
			
			if(node2.e==5)
			{
				
				array[i]=node2;
				for(j=i;j>0&&array[j].parent!=0;j--)
				{	
					array[j-1]=oilarray[array[j].parent];
				}
				
				node2.sign=1;
				
			}
			
			
		}

		if(node1.e<7&&(node1.e+node1.s>=7))
		{
			node1.s=node1.s+node1.e-7;
			node1.e=7;
			
			
			for(j=0;j<=i;j++)
			{
				if((node1.e==oilarray[j].e)&&(node1.s==oilarray[j].s))
					same=1;
			}
			if(same==1)
			{
				node1=topnode;
				same=0;
			}
			else
			{
				i++;
				
				oilarray[i]=node1;
				oilarray[i].self=i;
				oilarray[i].parent=topnode.self;
				oilqueue.push(oilarray[i]);
				node2=oilarray[i];
				node1=topnode;
				
			}
			
			if(node2.e==5)
			{
				
				array[i]=node2;
				for(j=i;j>0&&array[j].parent!=0;j--)
				{
					
					array[j-1]=oilarray[array[j].parent];
				}
				
				node2.sign=1;
				
			}
			
			
		}
		if(node1.s<3&&(node1.s+node1.e>=3))
		{
			
			node1.e=node1.e+node1.s-3;
			node1.s=3;
			
			
			for(j=0;j<=i;j++)
			{
				if((node1.e==oilarray[j].e)&&(node1.s==oilarray[j].s))
					same=1;
			}
			if(same==1)
			{
				node1=topnode;
				same=0;
			}
			else
			{
				i++;
				
				oilarray[i]=node1;
				oilarray[i].self=i;
				oilarray[i].parent=topnode.self;
				oilqueue.push(oilarray[i]);
				node2=oilarray[i];
				node1=topnode;
				
			}
			
			if(node2.e==5)
			{
				
				array[i]=node2;
				for(j=i;j>0&&array[j].parent!=0;j--)
				{
					
					array[j-1]=oilarray[array[j].parent];
				}
				
				node2.sign=1;
				
			}
			
			
		}
		
	}
	cout<<"the breadth_first result is:"<<endl;
    cout<<"(0,0,0)";
	for(int m=j;m<=i;m++)
		cout<<"("<<10-array[m].e-array[m].s<<","<<array[m].e<<","<<array[m].s<<")";
	
}