범위 우선 검색 (BFS + STL queue) 구현

2881 단어 알고리즘
너비 우선 검색 알고리즘 (광 도 우선 검색 이 라 고도 함) 은 가장 간편 한 그림 의 검색 알고리즘 중 하나 로 이 알고리즘 도 많은 중요 한 그림 의 알고리즘 원형 입 니 다.Dijkstra 단일 소스 최 단 경로 알고리즘 과 Prim 최소 생 성 트 리 알고리즘 은 너비 우선 검색 과 유사 한 사상 을 사용 합 니 다.그 별명 은 BFS 라 고도 하 는데 맹목적 인 검색 법 에 속 하 는데 그 목적 은 그림 의 모든 노드 를 체계적으로 전개 하고 검사 하여 결 과 를 찾 는 것 이다.결과 의 가능 한 위 치 를 고려 하지 않 고 결 과 를 찾 을 때 까지 그림 전 체 를 철저히 검색 한 다 는 얘 기다.
전체적인 사고: 출발점 에서 사방 으로 동시에 전진 하여 새로운 점 (ABCD) 을 얻 은 다음 에 새로운 점 을 각자 의 네 가지 새로운 방향 으로 확산 시 켜 중점 을 찾 을 때 까지 프로그램 이 끝 납 니 다.
코드 는 다음 과 같다.
#define  _CRT_SECURE_NO_WARNINGS 
#include 
#include 
#include 
#include 
using namespace std;
/************************************************************************/
/*                            (bfs)                              */
/************************************************************************/
enum {ROW=7,COL=7};

int map[ROW][COL] = {
	{ 0, 0, 1, 0, 1, 0, 1 },
	{ 1, 0, 0, 1, 0, 0, 1 },
	{ 1, 0, 1, 0, 0, 1, 0 },
	{ 1, 0, 0, 1, 0, 0, 1 },
	{ 0, 0, 0, 1, 0, 0, 1 },
	{ 1, 0, 1, 0, 0, 0, 1 },
	{ 1, 0, 0, 0, 1, 0, 1 },
};
int dir[4][2] = {
	{ -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }
};
int vis[ROW][COL] = { 0 };
struct Node
{
	int x;
	int y;
	int step;
	friend istream & operator>>(istream &is, Node &obj)
	{
		is >> obj.x >> obj.y;
		return is;
	}
	bool operator==(Node &obj)
	{
		if (this->x == obj.x&&this->y == obj.y)
			return true;//         ,     
		return false;//     
	}
};
int bfs(Node & fir, Node & dest)
{
	queue Q;
	Q.push(fir);
	vis[fir.x][fir.y] = true;
	while (!Q.empty())
	{
		Node cur =Q.front();
		if (cur == dest) return cur.step;
		Q.pop();
		for (int i = 0; i < 4; i++)
		{
			int new_x = cur.x + dir[i][0];
			int new_y = cur.y + dir[i][1];
			//        ,       ,       
			if (new_x >= 0 && new_x < ROW&&new_y >= 0 && new_y < COL&&!vis[new_x][new_y] && !map[new_x][new_y])
			{
				Node new_node = { new_x, new_y,cur.step+1};
				Q.push(new_node);//           
				vis[new_x][new_y] = true;
			}
		}
	}
	return 0;
	

}
void init()
{
	memset(vis, 0, sizeof(vis));
	for (int i = 0; i < ROW; i++)
	for (int j = 0; j < COL; j++)
	{
		if (map[i][j] == 2)
			map[i][j] = 0;
	}
}
void print_map()
{
	for (int i = 0; i < ROW; i++)
	{
		for (int j = 0; j < COL; j++)
			std::cout << map[i][j] << " ";
		std::cout << std::endl;
	}
}
int main(void)
{
	init();
	print_map();
	Node fir;
	Node dest;
	cin >> fir >> dest;
	fir.step = 1;
	int step = 0;
	if (map[fir.x][fir.y] && map[dest.x][dest.y])
	{
		cout << "        !" << endl;
	}
	else if (step=bfs(fir, dest))
	{
		cout << "      !"<

좋은 웹페이지 즐겨찾기