ACM_검색: 항주 전기 oj 2717: Catch That Cow

3853 단어 ACM_검색
제목 전송 문:http://acm.hdu.edu.cn/showproblem.php?pid=2717
제목 대의: 두 개의 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; }

좋은 웹페이지 즐겨찾기