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
    #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; }