POJ 3278 - Catch That Cow


问题描述

给定两个整数n和k

通过 n+1n-1n*2 这 3 种操作,使得 n==k

输出最少的操作次数

解题思路

水题,三入口的BFS

注意的地方有二:

  • 由于用于广搜的 队列数组 和 标记数组 相当大,如果定义这两个数组时把它们扔到局部去,编译是可以的,但肯定执行不了,提交就等RE吧。 大数组必须开为 全局 ,这是常识。。
  • 剪枝:直接广搜一样等着RE吧 (不剪枝的同学输入 n=0 k=100000 试试)。。。具体怎么剪枝看程序

AC 源码

//Memory Time 
//1292K   0MS 

#include<iostream>
using namespace std;

const int large=200030;

typedef class
{
    public:
        int x;
        int step;
}pos;

int n,k;
bool vist[large];   //数组较大,必须开为全局数组,不然肯定RE
pos queue[large];

void BFS(void)
{
    int head,tail;
    queue[head=tail=0].x=n;
    queue[tail++].step=0;

    vist[n]=true;

    while(head<tail)
    {
        pos w=queue[head++];

        if(w.x==k)
        {
            cout<<w.step<<endl;
            break;
        }

        if(w.x-1>=0 && !vist[w.x-1])     //w.x-1>=0  是剪枝
        {
            vist[w.x-1]=true;
            queue[tail].x=w.x-1;
            queue[tail++].step=w.step+1;
        }
        if(w.x<=k && !vist[w.x+1])     //w.x<=k  是剪枝
        {
            vist[w.x+1]=true;
            queue[tail].x=w.x+1;
            queue[tail++].step=w.step+1;
        }
        if(w.x<=k && !vist[2*w.x])     //w.x<=k  是剪枝
        {
            vist[2*w.x]=true;
            queue[tail].x=2*w.x;
            queue[tail++].step=w.step+1;
        }
    }

    return;
}

int main(void)
{
    while(cin>>n>>k)
    {
        memset(vist,false,sizeof(vist));
        BFS();
    }

    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 3083 - Children of the Candy Corn POJ 3083 - Children of the Candy Corn
POJ 3083 - Children of the Candy Corn Time: 1000MS Memory: 65536K 难度: 初级 分类: DFS 问题描述给定一个迷宫,S是起点,E是终点,# 是墙不可走,. 可以走 先输
2011-01-04
下一篇 
C++ 的自定义格式输出 C++ 的自定义格式输出
标准输出函数cout允许用户输出各种 标准数据类型 定义的数据,但是这种输出都是按标准格式输出的。有时,用户希望能改变输出格式,比如希望以十六进制输出100等,此时就必须用 自定义输出格式。 在C++头文件 iomanip 中包含了许多控
2010-11-24
  目录