POJ 3278第一道BFS 100題記念して
17337 ワード
タイトルは http://poj.org/problem?id=3278
このテーマの过ぎたのはやはり比较的に困难で、主に私が一気に最も良い方法でしていないためで、多くの时、やはり完全に区别していないでいつBFSを使って、いつDFSを使います
もう少しテーマをまとめてみようかな.でも、このテーマを作ったら100のテーマがあるんだから、がんばってね.ファイトFor oFFers
Source Code
Problem: 3278
User: hopeztm
Memory: 2308K
Time: 141MS
Language: C++
Result: Accepted Source Code
このテーマの过ぎたのはやはり比较的に困难で、主に私が一気に最も良い方法でしていないためで、多くの时、やはり完全に区别していないでいつBFSを使って、いつDFSを使います
もう少しテーマをまとめてみようかな.でも、このテーマを作ったら100のテーマがあるんだから、がんばってね.ファイトFor oFFers
Source Code
Problem: 3278
User: hopeztm
Memory: 2308K
Time: 141MS
Language: C++
Result: Accepted
#include <stdio.h>
#include <memory.h>
#include <queue>
using namespace std;
#define MAX_NUM 200003
#define MAX_INT 1000000000
#define MIN(x, y, z) (x < y ? x : y) < z ? (x < y ? x : y) : z
int num[MAX_NUM];
int visit[MAX_NUM];
int From, To;
int GetMinSteps(int i, int target)
{
queue<int> t;
t.push(i);
int current;
num[i] = 0;
visit[i] = true;
while(!t.empty())
{
current = t.front();
t.pop();
if(current == To)
break;
if( current - 1 >= 0 && !visit[current-1])
{
visit[current] = true;
num[current - 1] = min(num[current - 1], num[current] + 1);
t.push(current - 1);
}
if(current + 1 <= To && !visit[current + 1] )
{
visit[current + 1] = true;
num[current+1] = min(num[current + 1], num[current] + 1);
t.push(current + 1);
}
if(2 * current < 2 * To && !visit[2 * current] )
{
visit[2 * current ] = true;
num[current * 2] = min(num[current * 2], num[current] + 1);
t.push(2 * current);
}
}
return num[To];
}
int main()
{
while(scanf("%d%d", &From, &To) != EOF)
{
memset(visit, 0, sizeof(visit));
memset(num, 0x7F, sizeof(num));
printf("%d
", GetMinSteps(From, To));
}
return 0;
}