범위 우선 검색 (BFS + STL queue) 구현
2881 단어 알고리즘
전체적인 사고: 출발점 에서 사방 으로 동시에 전진 하여 새로운 점 (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 << " !"<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.