//Bfs.cpp
#include?“stdafx.h“
#include?“Bfs.h“
int?dir[4][2]={{01}{0-1}{10}{-10}};

void?Bfs::InitBfs（bool?**chessXY?size）
{
	m_size=size;
	m_chess=new?bool?*[m_size.x];
	m_visit=new?bool?*[m_size.x];
	m_parent=new?XY?*[m_size.x];

	for（int?i=0;i	{
		m_chess[i]=new?bool?[m_size.y];
		m_visit[i]=new?bool?[m_size.y];
		m_parent[i]=new?XY?[m_size.y];
	}
	for（int?i=0;i	{
		for（int?j=0;j		{
			m_chess[i][j]=*（（bool*）chess+m_size.y*i+j）;
			m_visit[i][j]=false;
			m_parent[i][j].x=-1;
			m_parent[i][j].y=-1;
		}
	}
	while（!m_que.empty（））
		m_que.pop（）;
}

bool?Bfs::CalcBfs（XY?stXY?en）
{
	queue?temque;
	m_visit[st.x][st.y]=true;
	temque.push（st）;
	XY?headnext;
	int?quesize;

	while（!temque.empty（））
	{
		quesize=temque.size（）;
		while（quesize--）
		{
			head=temque.front（）;
			temque.pop（）;
			if（head.x==en.x&&head.y==en.y）
			{
				//AfxMessageBox（L“HELLO“）;
				return?true;//已經達到目的了.
			}
			for（int?i=0;i<4;i++）
			{
				next.x=head.x+dir[i][0];?
				next.y=head.y+dir[i][1];
				if（next.x<0||（next.x>（m_size.x-1））||
					next.y<0||（next.y>（m_size.y-1））||
					m_chess[next.x][next.y]）
					continue;
				if（!m_visit[next.x][next.y]）
				{
					m_visit[next.x][next.y]=1;
					temque.push（next）;
					m_parent[next.x][next.y].x=head.x;
					m_parent[next.x][next.y].y=head.y;
				}
			}
		}
	}
	return?false;
}

void?Bfs::CalcQue（XY?en）
{
	if（en.x!=-1&&en.y!=-1）
	{
		CalcQue（m_parent[en.x][en.y]）;
		m_que.push（en）;
	}
}

void?Bfs::EetBfs（XY?stXY?en）
{
	CalcBfs（sten）;
	CalcQue（en）;
	m_que.pop（）;//彈出沒用的起始點..
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2014-02-04?10:51??SmartSnake\
?????目錄???????????0??2014-02-04?10:51??SmartSnake\Release\
?????文件?????3509760??2014-02-02?17:22??SmartSnake\Release\SmartSnake.exe
?????目錄???????????0??2014-02-04?10:51??SmartSnake\SmartSnake\
?????文件?????????897??2014-01-27?13:58??SmartSnake\SmartSnake.sln
?????文件????????1683??2014-02-01?23:43??SmartSnake\SmartSnake\Bfs.cpp
?????文件?????????532??2014-02-01?22:58??SmartSnake\SmartSnake\Bfs.h
?????文件????????3248??2014-01-27?13:57??SmartSnake\SmartSnake\ReadMe.txt
?????目錄???????????0??2014-02-04?10:51??SmartSnake\SmartSnake\res\
?????文件????????1974??2014-01-27?16:04??SmartSnake\SmartSnake\resource.h
?????文件???????67777??2013-06-05?10:20??SmartSnake\SmartSnake\res\SmartSnake.ico
?????文件?????????676??2014-01-27?13:57??SmartSnake\SmartSnake\res\SmartSnake.rc2
?????文件????????1859??2014-01-27?13:57??SmartSnake\SmartSnake\SmartSnake.cpp
?????文件?????????450??2014-01-27?13:57??SmartSnake\SmartSnake\SmartSnake.h
?????文件????????9202??2014-02-02?11:21??SmartSnake\SmartSnake\SmartSnake.rc
?????文件????????6306??2014-02-01?18:39??SmartSnake\SmartSnake\SmartSnake.vcxproj
?????文件????????2534??2014-02-01?18:39??SmartSnake\SmartSnake\SmartSnake.vcxproj.filters
?????文件????????2322??2014-01-27?22:49??SmartSnake\SmartSnake\Snake.cpp
?????文件?????????859??2014-01-27?16:37??SmartSnake\SmartSnake\Snake.h
?????文件????????7983??2014-02-02?17:22??SmartSnake\SmartSnake\SnakeDlg.cpp
?????文件????????1200??2014-02-02?16:32??SmartSnake\SmartSnake\SnakeDlg.h
?????文件?????????143??2014-01-27?13:57??SmartSnake\SmartSnake\stdafx.cpp
?????文件?????????856??2014-01-27?13:57??SmartSnake\SmartSnake\stdafx.h
?????文件?????????234??2014-01-27?13:57??SmartSnake\SmartSnake\targetver.h
?????文件?????????657??2013-04-21?15:48??SmartSnake\SmartSnake\xp.manifest