sawenumimpl.h

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

#pragma once

using namespace std;

/****************************************************************************************************************/
//class SAWLattice
class SAWLattice
{
public:
	SAWLattice(int len) : m_len(len), m_table(len * 2 - 1, vector<int>(len * 2 - 1, 0)) {}

	//x->+, y V+
	int GetAt(int x, int y) const
	{
		return m_table[y + m_len - 1][x + m_len - 1];
	}

	void SetAt(int x, int y, int val)
	{
		m_table[y + m_len - 1][x + m_len - 1] = val;
	}

	void Reset() { m_table = vector< vector<int> >(m_len * 2 - 1, vector<int>(m_len * 2 - 1, 0)); }

private:
	vector< vector<int> > m_table;
	int m_len;
};

/****************************************************************************************************************/
//class SAWEnumThread
enum From {up = 0, right = 1, down = 2, left = 3};

class SAWEnumThread
{
public:
	SAWEnumThread(int len) : m_len(len), m_table(len + 1), m_cnt(0) {}
	__int64 GetCount()			{return m_cnt;}
	SAWLattice & Init(int curLen, CPoint &ptStart, From from); 

//	enum {modRDL = 0, modRDR = 1, modRDD = 2, modOther = 3};

	void IterEnum(CPoint curPos, From from);
	void StartEnum()				{IterEnum(m_ptStart, m_frStart);}
	void GoUp(CPoint curPos);
	void GoDown(CPoint curPos);
	void GoLeft(CPoint curPos);
	void GoRight(CPoint curPos);

private:
	//Only used by IterEnum
	__int64		m_cnt;
	int			m_curLen;
	const int	m_len;
	SAWLattice	m_table;

	CPoint	m_ptStart;
	From	m_frStart;
};

/****************************************************************************************************************/
//class SAWEnum
typedef struct tagPROCPARAM
{
	SAWEnumThread	*pObj;
	CEvent			ev;
}PROCPARAM, *LPPROCPARAM;

class SAWEnum
{
public:
	SAWEnum(int len, BOOL bMutiThread);
	~SAWEnum();

	void DistributeWorks();
	__int64 GetPathCount();

private:
	void PrepareRDL();
	void PrepareRDR();
	void PrepareRDD();
	void PrepareRRD();
	void PrepareOther(int len);

	static UINT StartProc(LPVOID pParam);

	SAWEnumThread	m_etRDL;
	SAWEnumThread	m_etRDR;
	SAWEnumThread	m_etRDD;
	SAWEnumThread	m_etRRD;
	SAWEnumThread	m_etOther;
	PROCPARAM		m_pp[4];

	__int64 m_nOtherCnt;
	const int m_len;
	BOOL m_bMutiThread;

};