sawenumimpl.cpp.bak

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

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

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


// The one and only application object

//CWinApp theApp;

using namespace std;

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 SAWEnum
{
public:
	SAWEnum(int len) : m_len(len), m_table(len) {}
	__int64 GetPathCount();
	void ShowTable();

private:
	enum From {up = 0, right = 1, down = 2, left = 3};

private:
	CPoint PrepareIter(int index);
	void IterEnum(CPoint curPos, From from);
	void GoUp(CPoint curPos);
	void GoDown(CPoint curPos);
	void GoLeft(CPoint curPos);
	void GoRight(CPoint curPos);

	//Only used by IterEnum
	__int64		m_cnt;
	__int64		m_curLen;

private:
	int			m_len;
	SAWLattice	m_table;
};

void SAWEnum::ShowTable()
{
	for(int y = 1 - m_len; y < m_len; ++y)
	{
		for(int x = 1 - m_len; x < m_len; ++x)
		{
			cout << m_table.GetAt(x, y) << ' ';
		}
		cout << endl;
	}
	cout << endl;
}

CPoint SAWEnum::PrepareIter(int index)
{
	m_table.Reset();
	for(int i = 0; i < index - 2; ++i)
	{
		m_table.SetAt(0, i, 1);
	}
	m_table.SetAt(0, i, 1);
	m_table.SetAt(1, i, 1);

	m_cnt = 0;
	m_curLen = index;

	return CPoint(1, i);
}

__int64 SAWEnum::GetPathCount()
{
	__int64 totalCnt = 0;
	if(m_len <= 0)
	{
		return 0;
	}
	if(m_len == 1)
	{
		return 1;
	}
	if(m_len == 2)
	{
		return 4;
	}

	for(int i = m_len; i >= 3; --i)
	{
		IterEnum(PrepareIter(i), left);
		totalCnt += m_cnt * 2;
		m_cnt = 0;
		cout << i << endl;
	}

	return (totalCnt + 1) * 4;
}

void SAWEnum::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 SAWEnum::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 SAWEnum::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 SAWEnum::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 SAWEnum::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;
		}
	}
}

int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
	SAWEnum se(25);
	printf("%I64d", se.GetPathCount());
	getch();
	return 0;
}
/*
int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
	int nRetCode = 0;

	// initialize MFC and print and error on failure
	if (!AfxWinInit(::GetModuleHandle(NULL), NULL, ::GetCommandLine(), 0))
	{
		// TODO: change error code to suit your needs
		_tprintf(_T("Fatal Error: MFC initialization failed\n"));
		nRetCode = 1;
	}
	else
	{
		// TODO: code your application's behavior here.

	}

	return nRetCode;
}
*/