POJ 3278 Catch That Cow

解法

bfs

ソースコード

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);

    const int inf = ten(7);
    int d[2 * ten(5) + 100];
    fill(d, d + 2 * ten(5), inf);
    queue<int> q;
    d[n] = 0;
    q.push(n);
    while (!q.empty())
    {
	int p = q.front();
	q.pop();
	int nd = d[p] + 1;
	int to[] = { p - 1, p + 1, 2 * p };
	rep(i, 3)
	{
	    if (to[i] >= 0 && to[i] < ten(5) + 10)
	    {
		if (nd < d[to[i]])
		{
		    d[to[i]] = nd;
		    q.push(to[i]);
		}
	    }
	}
    }
    printf("%d\n", d[k]);
}