ACM_검색: 항주 전기 oj 2717: Catch That Cow
3853 단어 ACM_검색
제목 대의: 두 개의 x 축 방향의 위 치 를 정 하고 농민 들 은 세 가지 방식 이 있 습 니 다. bfs 로 가장 짧 은 경 로 를 찾 으 면 됩 니 다.
AC 코드:
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define Size 100005
struct Node
{
int x;
int step;
};
int visit[Size];
int m, n;
int bfs()
{
queue temp;
Node s, now, next;
s.x = m;
s.step = 0;
temp.push(s);
visit[s.x] = 1;
while (!temp.empty())
{
now = temp.front();
temp.pop();
if (now.x == n)
{
return now.step;
}
for (int i = 0; i < 3; ++i)
{
if (i == 0)
next.x = now.x + 1;
else if (i == 1)
next.x = now.x - 1;
else if (i == 2)
next.x = 2 * now.x;
// .
if (next.x >= 0 && next.x < Size && visit[next.x] == 0)
{
visit[next.x] = 1;
next.step = now.step + 1;
temp.push(next);
}
}
}
return -1;
}
int main()
{
while (scanf("%d%d", &m,&n) != EOF)
{
if (m == n)
{
printf("0
");
continue;
}
memset(visit, 0, sizeof(visit));
printf("%d
", bfs());
}
return 0;
}