杭电 hdu 2717 Catch That Cow

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.

URL   : http://acm.hdu.edu.cn/showproblem.php?pid=2717
Name  : 2717 Catch That Cow

Date  :Sunday, August 14, 2011
Time Stage : 1 hours less

Result:
4414484	2011-08-14 20:37:44 Accepted 2717 15MS 776K 1586 B C++	pyy


Test Data:

Review:

//----------------------------------------------------------------------------*/

#include <queue>
#include <stdio.h>
#include <string.h>
#include <conio.h>

using namespace std ;

#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))

#define infinity	0x7f7f7f7f
#define minus_inf	0x80808080

#define MAXSIZE 100009

int start, end ;
int line[MAXSIZE] ;

void bfs ()
{
	int i, j ;
	int tmp, next ;
	queue<int> q ;

	memset (line, 0, sizeof (line)) ;
	q.push (start) ;
	line[start] = 1 ;

	while (!q.empty ())
	{
		tmp = q.front () ;
		q.pop () ;

		if (tmp == end)
			break ;

		next = tmp - 1 ;
		if (next >= 0 && !line[next])
		{
			q.push (next) ;
			line[next] = line[tmp] + 1 ;
		}

		next = tmp + 1 ;
		if (!line[next])
		{
			q.push (next) ;
			line[next] = line[tmp] + 1 ;
		}

		next = tmp * 2 ;
		// 这句：next - end < end - tmp 本来是剪枝用的，可是加不加好像
		// 用时一样……
		// 一开始这里写成了 next – 17 < 17 – tmp 结果一直错……真是太大意了！
		if (next <= 100000 && next - end < end - tmp && !line[next])
		{
			q.push (next) ;
			line[next] = line[tmp] + 1 ;
		}
	}
}

int main ()
{
	int i, j ;
	while (scanf ("%d%d", &start, &end) != EOF)
	{
		if (start >= end)
			line[end] = start - end + 1;
		else
			bfs () ;
		printf ("%d\n", line[end] - 1) ;
	}
	return 0 ;
}

评论

3 楼 gzhu_101majia 2011-08-14  

 

2 楼 gzhu_101majia 2011-08-14  

做些难度大的啊，这些比较简单

1 楼 基德KID.1412 2011-08-14  

Y神啊 顶上