sawenumimpl.cpp

一个高效的自回避行走路径枚举程序。运用了多线程分配分支任务

// SAWEnumImpl.cpp
//

#include "stdafx.h"
#include "SAWEnumImpl.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#endif

/****************************************************************************************************************/
//class SAWEnumThread
SAWLattice & SAWEnumThread::Init(int curLen, CPoint &ptStart, From from)
{
	m_cnt = 0; 
	m_table.Reset(); 
	m_table.SetAt(0, 0, 1); 
	m_curLen = curLen; 
	m_ptStart = ptStart; 
	m_frStart = from;
	return m_table;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void SAWEnumThread::GoUp(CPoint curPos)
{
	--curPos.y;
	if(m_table.GetAt(curPos.x, curPos.y) == 0)
	{
		m_table.SetAt(curPos.x, curPos.y, 1);
		++m_curLen;
		IterEnum(curPos, down);
		m_table.SetAt(curPos.x, curPos.y, 0);
		--m_curLen;
	}
}

void SAWEnumThread::GoDown(CPoint curPos)
{
	++curPos.y;
	if(m_table.GetAt(curPos.x, curPos.y) == 0)
	{
		m_table.SetAt(curPos.x, curPos.y, 1);
		++m_curLen;
		IterEnum(curPos, up);
		m_table.SetAt(curPos.x, curPos.y, 0);
		--m_curLen;
	}
}

void SAWEnumThread::GoLeft(CPoint curPos)
{
	--curPos.x;
	if(m_table.GetAt(curPos.x, curPos.y) == 0)
	{
		m_table.SetAt(curPos.x, curPos.y, 1);
		++m_curLen;
		IterEnum(curPos, right);
		m_table.SetAt(curPos.x, curPos.y, 0);
		--m_curLen;
	}
}

void SAWEnumThread::GoRight(CPoint curPos)
{
	++curPos.x;
	if(m_table.GetAt(curPos.x, curPos.y) == 0)
	{
		m_table.SetAt(curPos.x, curPos.y, 1);
		++m_curLen;
		IterEnum(curPos, left);
		m_table.SetAt(curPos.x, curPos.y, 0);
		--m_curLen;
	}
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void SAWEnumThread::IterEnum(CPoint curPos, From from)
{
	if(m_curLen == m_len)
	{
		++m_cnt;
		return;
	}
	else if(m_curLen == m_len - 1)
	{
		switch(from)
		{
		case left:
			m_cnt += 3 - m_table.GetAt(curPos.x, curPos.y - 1)
					   - m_table.GetAt(curPos.x, curPos.y + 1)
					   - m_table.GetAt(curPos.x + 1, curPos.y);
			break;
		case up:
			m_cnt += 3 - m_table.GetAt(curPos.x - 1, curPos.y)
					   - m_table.GetAt(curPos.x, curPos.y + 1)
					   - m_table.GetAt(curPos.x + 1, curPos.y);
			break;
		case right:
			m_cnt += 3 - m_table.GetAt(curPos.x, curPos.y - 1)
					   - m_table.GetAt(curPos.x, curPos.y + 1)
					   - m_table.GetAt(curPos.x - 1, curPos.y);
			break;
		case down:
			m_cnt += 3 - m_table.GetAt(curPos.x, curPos.y - 1)
					   - m_table.GetAt(curPos.x - 1, curPos.y)
					   - m_table.GetAt(curPos.x + 1, curPos.y);
			break;
		}
	}
	else
	{
		switch(from)
		{
		case left:
			GoRight(curPos);
			GoUp(curPos);
			GoDown(curPos);
			break;
		case up:
			GoLeft(curPos);
			GoRight(curPos);
			GoDown(curPos);
			break;
		case right:
			GoLeft(curPos);
			GoUp(curPos);
			GoDown(curPos);
			break;
		case down:
			GoLeft(curPos);
			GoRight(curPos);
			GoUp(curPos);
			break;
		}
	}
}

/****************************************************************************************************************/
//class SAWEnum

SAWEnum::SAWEnum(int len, BOOL bMutiThread) : m_len(len), m_bMutiThread(bMutiThread), m_etRDL(len), m_etRDR(len), m_etRDD(len), m_etRRD(len), m_etOther(len), m_nOtherCnt(0)
{
}

SAWEnum::~SAWEnum()
{
}

UINT SAWEnum::StartProc(LPVOID pParam)
{
	PROCPARAM *pp = (PROCPARAM *)pParam;
	SAWEnumThread *pObj = pp->pObj;
	pp->ev.ResetEvent();
	pObj->StartEnum();
	pp->ev.SetEvent();
	return 0;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void SAWEnum::PrepareRDL()
{
	SAWLattice &lts = m_etRDL.Init(3, CPoint(0, 1), right);
	lts.SetAt(1, 0, 1);
	lts.SetAt(1, 1, 1);
	lts.SetAt(0, 1, 1);
	return;
}

void SAWEnum::PrepareRDR()
{
	SAWLattice &lts = m_etRDR.Init(3, CPoint(2, 1), left);
	lts.SetAt(1, 0, 1);
	lts.SetAt(1, 1, 1);
	lts.SetAt(2, 1, 1);
	return;
}

void SAWEnum::PrepareRDD()
{
	SAWLattice &lts = m_etRDD.Init(3, CPoint(1, 2), up);
	lts.SetAt(1, 0, 1);
	lts.SetAt(1, 1, 1);
	lts.SetAt(1, 2, 1);
	return;
}

void SAWEnum::PrepareRRD()
{
	SAWLattice &lts = m_etRRD.Init(3, CPoint(2, 1), up);
	lts.SetAt(1, 0, 1);
	lts.SetAt(2, 0, 1);
	lts.SetAt(2, 1, 1);
	return;
}

//Generate RRRD, RRRRD....
void SAWEnum::PrepareOther(int len)
{
	SAWLattice &lts = m_etOther.Init(len, CPoint(len - 1, 1), up);
	for(int i = 1; i < len; ++i)
	{
		lts.SetAt(i, 0, 1);
	}
	lts.SetAt(len - 1, 1, 1);
	return;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
__int64 SAWEnum::GetPathCount()
{
	switch(m_len)
	{
	case 0:
		return 1;
	case 1:
		return 4;
	case 2:
		return 12;
	case 3:
		return 36;
	}

	if(m_bMutiThread)
	{
		HANDLE h[4] = {m_pp[0].ev, m_pp[1].ev, m_pp[2].ev, m_pp[3].ev};
		if(WaitForMultipleObjects(4, h, TRUE, 0) == WAIT_TIMEOUT)
		{
			return -1;
		}
		else
		{
			return ((m_etRDL.GetCount() + m_etRDR.GetCount() + m_etRDD.GetCount() 
				+ m_etRRD.GetCount() + m_nOtherCnt) * 2 + 1) * 4;
		}
	}
	else
	{
		return (m_nOtherCnt * 2 + 1) * 4;
	}
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void SAWEnum::DistributeWorks()
{
	CWinThread *pThread;
	if(m_bMutiThread)
	{
		PrepareRDL();
		m_pp[0].pObj = &m_etRDL;
		pThread = AfxBeginThread(SAWEnum::StartProc, &m_pp[0], THREAD_PRIORITY_HIGHEST);
		SetThreadIdealProcessor(pThread->m_hThread, 0);

		PrepareRDR();
		m_pp[1].pObj = &m_etRDR;
		pThread = AfxBeginThread(SAWEnum::StartProc, &m_pp[1], THREAD_PRIORITY_HIGHEST);
		SetThreadIdealProcessor(pThread->m_hThread, 0);

		PrepareRDD();
		m_pp[2].pObj = &m_etRDD;
		pThread = AfxBeginThread(SAWEnum::StartProc, &m_pp[2], THREAD_PRIORITY_HIGHEST);
		SetThreadIdealProcessor(pThread->m_hThread, 1);

		PrepareRRD();
		m_pp[3].pObj = &m_etRRD;
		pThread = AfxBeginThread(SAWEnum::StartProc, &m_pp[3], THREAD_PRIORITY_HIGHEST);
		SetThreadIdealProcessor(pThread->m_hThread, 1);

		m_nOtherCnt = 0;
		for(int i = 4; i <= m_len; ++i)
		{
			PrepareOther(i);
			m_etOther.StartEnum();
			m_nOtherCnt += m_etOther.GetCount();
		}
	}
	else
	{
		m_nOtherCnt = 0;
		for(int i = 2; i <= m_len; ++i)
		{
			PrepareOther(i);
			m_etOther.StartEnum();
			m_nOtherCnt += m_etOther.GetCount();
		}
	}
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////