mcprocview.cpp

人工智能实验---求解传教士与野人问题,并画出状态图做动态演示.

// MCProcView.cpp : implementation of the CMCProcView class
//

#include "stdafx.h"
#include "MCProc.h"

#include "MCProcDoc.h"
#include "MCProcView.h"

#include "MCLView.h"
#include "MCRView.h"

#include "InputDlg.h"
#include "MCProb.h"

#include <math.h>

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CMCProcView
const int sx=50,sy=50;
const int dx=80;
const int r=25;
const int dy=200;

int iOps=0;

Node** node=NULL;
CPoint** points=NULL;
Operator* Path=NULL;

CPen* pBluePen=NULL;
CPen* pRedPen=NULL;
CPen* pGreenPen=NULL;
CBrush* pYellowB=NULL;
CBrush* pBlueB=NULL;
CBrush* pPinkB=NULL;

IMPLEMENT_DYNCREATE(CMCProcView, CScrollView )

BEGIN_MESSAGE_MAP(CMCProcView, CScrollView)
//{{AFX_MSG_MAP(CMCProcView)
ON_COMMAND(ID_SOLVE, OnSolve)
ON_WM_TIMER()
//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMCProcView construction/destruction

CMCProcView::CMCProcView()
{
	// TODO: add construction code here
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>人数和船的承载量
	m_N=0;
	m_V=0;
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>定义画笔画刷
	pBluePen=new CPen(PS_SOLID,2,RGB(0,0,255));
	pRedPen=new CPen(PS_SOLID,2,RGB(255,0,0));
	pGreenPen=new CPen(PS_SOLID,2,RGB(0,255,0));
	pYellowB=new CBrush(RGB(255,255,0));
	pBlueB=new CBrush(RGB(0,255,255));
	pPinkB=new CBrush(RGB(255,0,255));
}

CMCProcView::~CMCProcView()
{
	delete pBluePen;
	delete pRedPen;
	delete pGreenPen;
	delete pYellowB;
	delete pBlueB;
	delete pPinkB;
}

BOOL CMCProcView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs
	
	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CMCProcView drawing

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
//     ( i , j )===========>( m , c , b )
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
void exchange(int& m,int& c,int& b,int i,int j,int N)
{
	b=i;
	int x,y;
	x=j/N;y=j%N;
	if(b==1)
	{
		switch(x)
		{
		case 0:
			m=0;c=y+1;
			break;
		case 1:
			m=y+1;c=y+1;
			break;
		case 2:
			m=N;c=y;
			break;
		}
	}
	else
	{
		switch(x)
		{
		case 0:
			m=0;c=y+1;
			break;
		case 1:
			m=y;c=y;
			break;
		case 2:
			m=N;c=y;
			break;
		}
	}
}

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
//     ( m , c , b )===========>( i , j )
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
bool exchange(int& i,int& j,int m,int c,bool b,int N)
{
	if(m<0 || m>N || c<0 || c>N)
		return 0;
	bool flag=1;
    i=b;
	if(b)
	{
		if(m==0)
		{
			j=c-1;
		}
		else if(m==c&&c!=0)
		{
            j=N+c-1;
		}
		else if(m==N)
		{
			j=N+N+c;
		}
		else
		{
			flag=0;
		}
	}
	else
	{
		if(m==N)
		{
            j=N+N+c;
		}
		else if(m==c&&c!=N)
		{
			j=N+c;
		}
		else if(m==0)
		{
			j=c-1;
		}
		else
		{
			flag=0;
		}
	}
	return flag;
}

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
//     画线和箭头函数
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

void DrawArrow(CDC* pDC,CPoint& start,CPoint& end)
{
	int dx,dy,x,y;
	double dq;
	
	dx=start.x-end.x;
	dy=start.y-end.y;
	
	dx=dx-dy;
	dy=dx+2*dy;
	
    dq=sqrt(dx*dx+dy*dy);
	x=int(10*dx/dq);
	y=int(10*dy/dq);
	
	pDC->MoveTo(end);
	pDC->LineTo(end.x+x,end.y+y);
    pDC->MoveTo(end);
	pDC->LineTo(end.x+y,end.y-x);
}


void DrawLine(CDC* pDC,CPoint& start,CPoint& end,int r)
{
	int dx,dy;
	double q;
	CPoint newstart,newend;
	dx=start.x-end.x;
	dy=start.y-end.y;
	
	q=sqrt(dx*dx+dy*dy);
	int tempx=int(dx*r/q);
	int tempy=int(dy*r/q);
	newstart.x=start.x-tempx;
	newstart.y=start.y-tempy;
	
	newend.x=end.x+tempx;
	newend.y=end.y+tempy;
	
	pDC->MoveTo(newstart);
	pDC->LineTo(newend);
}

/*>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
检查是否合法的边
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>*/

bool CheckOP(int m0,int m1,int c0,int c1,int V)
{
	int dm=m1-m0;
	int dc=c1-c0;
	if(dm<0||dc<0)
		return 0;
	if(dm==0&&dc==0)
		return 0;
	if(dm+dc>V)
		return 0;
	if(dm==0||dc==0||dm>=dc)
	{
		return 1;
	}
	return 0;
}

/*>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
插入节点,为Build调用建立邻接表
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>*/

void InsertNode(int i,int j)
{
    Node* pTemp=NULL;
	pTemp=new Node;
	pTemp->j=j;
	pTemp->b=0;
	pTemp->next=NULL;
	if(node[i]!=NULL)
	{
		pTemp->next=node[i];
	}
	node[i]=pTemp;
}

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
//标志走过的边
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

void SetFlag(int j0,int j1)
{
	Node* pTemp=NULL;
	pTemp=node[j0];
	while(pTemp)
	{
		if(pTemp->j==j1)
			pTemp->b=1;
		pTemp=pTemp->next;
	}
}

/*>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
建立邻接表
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>*/

void Build(int N,int V)
{
	int i,j;
	int m0,m1,c0,c1,b0,b1;
	int n=3*N;
	node=new Node*[n];
	for(i=0;i<n;i++)
	{
		node[i]=NULL;
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			exchange(m1,c1,b1,1,i,N);
			exchange(m0,c0,b0,0,j,N);
			if(CheckOP(m0,m1,c0,c1,V))
			{
				InsertNode(i,j);
			}
		}
	}
	
	points=new CPoint*[2];
	for(i=0;i<2;i++)//建立点坐标
	{
		points[i]=new CPoint[n];
	}
	for(i=0;i<2;i++)//画节点
	{
		for(j=0;j<n;j++)
		{
			points[i][j].x=sx+j*dx;
			points[i][j].y=sy+i*dy;
		}
	}
}

/****************************************************************
释放内存空间
*****************************************************************/
void Destroy(int N)
{
	int i;
	int n=3*N;
	if(node!=NULL)
	{
		Node* pTemp=NULL;
		for(i=0;i<n;i++)
		{
			while(node[i])
			{
				pTemp=node[i];
				node[i]=node[i]->next;
				delete pTemp;
			}
		}
		delete []node;
		node=NULL;
	}
	
	if(points!=NULL)
	{
		for(i=0;i<2;i++)
		{
			delete []points[i];
		}
		delete []points;
		points=NULL;
	}
	
	if(Path!=NULL)
	{
		delete []Path;
		Path=NULL;
	}
}

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>画图

void CMCProcView::OnDraw(CDC* pDC)
{
	CMCProcDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
	bool flag=1;
	int n=3*m_N;
	int m,c,b,i,j;
	CString str;
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>画节点
	for(i=0;i<2;i++)
	{
		for(j=0;j<n;j++)
		{
			CPen* pOldPen=NULL;
			CBrush* pOldBrush=NULL;
			if(i==0&&j==m_N)//终节点
			{
				pOldPen=pDC->SelectObject(pRedPen);
				pOldBrush=pDC->SelectObject(pYellowB);
			}
			else if(i==1&&j==2*m_N-1)//开始节点
			{
				pOldPen=pDC->SelectObject(pGreenPen);
				pOldBrush=pDC->SelectObject(pBlueB);
			}
			else//一般节点
			{
				pOldPen=pDC->SelectObject(pBluePen);
				pOldBrush=pDC->SelectObject(pPinkB);
			}
			exchange(m,c,b,i,j,m_N);
			str.Format("(%d,%d,%d)",m,c,b);
			int tempx=points[i][j].x;
			int tempy=points[i][j].y;
			pDC->Ellipse(CRect(tempx-r,tempy-r,tempx+r,tempy+r));
			pDC->SetBkMode(TRANSPARENT);
			pDC->DrawText(str,CRect(tempx-r,tempy-r,tempx+r,tempy+r),DT_SINGLELINE|DT_VCENTER|DT_CENTER);
			pDC->SelectObject(pOldPen);
			pDC->SelectObject(pOldBrush);
		}
	}
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>连线
	Node* pTemp=NULL;
	for(i=0;i<n;i++)
	{
        pTemp=node[i];
		while(pTemp)
		{
			CPen* pOldPen=NULL;
			if(pTemp->b)
			{
				pOldPen=pDC->SelectObject(pRedPen);
			}
			else
			{
				pOldPen=pDC->SelectObject(pBluePen);
			}
			DrawLine(pDC,points[1][i],points[0][pTemp->j],r);
			pTemp=pTemp->next;
			pDC->SelectObject(pOldPen);
		}
	}
}

/////////////////////////////////////////////////////////////////////////////
// CMCProcView diagnostics

#ifdef _DEBUG
void CMCProcView::AssertValid() const
{
	CView::AssertValid();
}

void CMCProcView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CMCProcDoc* CMCProcView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CMCProcDoc)));
	return (CMCProcDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CMCProcView message handlers
/*********************************************************************
操作线程函数
*********************************************************************/
UINT MCFunc( LPVOID pParam )
{
	CMCProcView* pView=(CMCProcView*)pParam;
	MCProb m_mc;
	m_mc.Init();
	if(m_mc.MCOprate(pView->m_N,pView->m_V))
	{
		Path=m_mc.path;
		iOps=m_mc.ops;
		AfxMessageBox("问题解决!现在开始演示!");
		pView->InitialData();
		pView->SetTimer(1,500,NULL);
	}
	else 
	{
		AfxMessageBox("问题无解!");
	}
	return 0;
}

/**********************************************************************
响应函数
***********************************************************************/
void CMCProcView::OnSolve() 
{
	// TODO: Add your command handler code here
	Destroy(m_N);
	CInputDlg dlg;
	if(dlg.DoModal()==IDOK)
	{
		m_N=dlg.m_mEdit;
		m_V=dlg.m_cEdit;
	}
	else
	{
		return;
	}
	Build(m_N,m_V);
	//画图
	this->Invalidate();
	int i=0;
	CMCProcDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	POSITION pos = pDoc->GetFirstViewPosition();
	CView* pView[3]; 
	while (pos != NULL)
	{
		pView[i++] = pDoc->GetNextView(pos);
	}
	((CMCLView*)pView[1])->DeleteAllItems();
	((CMCRView*)pView[2])->DeleteAllItems();
	AfxBeginThread(MCFunc,(LPVOID)this);
}

/*************************************************************************
定时器响应函数,0.5s响应一次
*************************************************************************/
void CMCProcView::OnTimer(UINT nIDEvent) 
{
	// TODO: Add your message handler code here and/or call default
	if(nIDEvent==1)
	{
		//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>计算显示数据
		ST st;
		st.m=m_stL.m+Path[m_i].m;
		st.c=m_stL.c+Path[m_i].c;
		st.b=!m_stL.b;
		int i0,j0,i1,j1;
		
		if(m_stL.b==1)
		{
			exchange(i0,j0,m_stL.m,m_stL.c,m_stL.b,m_N);
			exchange(i1,j1,st.m,st.c,st.b,m_N);
			SetFlag(j0,j1);
		}
		else
		{
			exchange(i0,j0,m_stL.m,m_stL.c,m_stL.b,m_N);
			exchange(i1,j1,st.m,st.c,st.b,m_N);
			SetFlag(j1,j0);
		}
		
		//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>动态显示操作过程
		CClientDC dc(this);
		OnPrepareDC(&dc);
		CPen* pOldPen=dc.SelectObject(pRedPen);
		DrawLine(&dc,points[i0][j0],points[i1][j1],r);
		dc.SelectObject(pOldPen);
		
		//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>获取数据
		CString strPre,strOp,strPos;
		CString strLeft,strRight;
		strPre.Format("(%d,%d,%d)",m_stL.m,m_stL.c,m_stL.b);
		strOp.Format("(%d,%d)",Path[m_i].m,Path[m_i].c);
		strPos.Format("(%d,%d,%d)",st.m,st.c,st.b);
		strLeft.Format("(%d,%d)",st.m,st.c);
		strRight.Format("(%d,%d)",m_N-st.m,m_N-st.c);
		//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>显示数据
		int i=0;
		CMCProcDoc* pDoc = GetDocument();
		ASSERT_VALID(pDoc);
		POSITION pos = pDoc->GetFirstViewPosition();
		CView* pView[3]; 
		while (pos != NULL)
		{
			pView[i++] = pDoc->GetNextView(pos);
		}
		((CMCLView*)pView[1])->AddItem(strPre,strOp,strPos);
		((CMCRView*)pView[2])->AddItem(strLeft,strRight);
		
		//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>如果操作完成,停止定时器
		if(m_i<iOps-1)
		{
			m_i++;
		}
		else 
		{
			KillTimer(1);
		}
		m_stL=st;
	}
	
	CView::OnTimer(nIDEvent);
}

void CMCProcView::OnInitialUpdate() 
{
	CScrollView::OnInitialUpdate();
	
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>设置视窗范围
	CRect rt;
	GetClientRect(&rt);
	SetScrollSizes(MM_TEXT,CSize(rt.Width()+10000,rt.Height()));
}

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>初始化显示数据
void CMCProcView::InitialData()
{
	m_stL.m=m_N;
    m_stL.c=m_N;
	m_stL.b=1;
	m_i=0;
}