POJ 2506 高精度+递推

9月 14

题目大意就是有$2 \times 1$和$2 \times 2$两种规格的地板，现要拼$2 \times n$的形状，共有多少种情况，首先要做这道题目要先对递推有一定的了解。
假设我们已经铺好了$2 \times (n-1)$的情形，则要铺到$2 \times n$则只能用$2 \times 1$的地板
假设我们已经铺好了$2 \times (n-2)$的情形，则要铺到$2 \times n$则可以选择1个$2 \times 2$或两个$2 \times 1$，故可能有下列三种铺法

其中要注意到第三个会与铺好$2 \times (n-1)$的情况重复，故不可取，故可以得到递推式$a_i=2a_{i-2}+a_{i-1}$

然后就是高精度部分，可直接用高精度的模板

直接套用模板就1A了，只是简单的递推题，算是练习套模板能力或验证模板的正确性吧！

poj2506 Tilingview raw

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include <deque>
#include <vector>
using namespace std;

const int Base=1000000000;  
const int Capacity=100;  
typedef long long huge;    

struct BigInt{  
     int Len;  
     int Data[Capacity];  
     BigInt() : Len(0) {}  
     BigInt (const BigInt &V) : Len(V.Len) { memcpy (Data, V.Data, Len*sizeof*Data);}  
     BigInt(int V) : Len(0) {for(;V>0;V/=Base) Data[Len++]=V%Base;}  
     BigInt &operator=(const BigInt &V) {Len=V.Len; memcpy(Data, V.Data, Len*sizeof*Data); return *this;}  
     int &operator[] (int Index) {return Data[Index];}  
     int operator[] (int Index) const {return Data[Index];}  
};

BigInt operator+(const BigInt &A,const BigInt &B){  
     int i,Carry(0);  
     BigInt R;  
     for(i=0;i<A.Len||i<B.Len||Carry>0;i++){  
         if(i<A.Len) Carry+=A[i];  
         if(i<B.Len) Carry+=B[i]; 
         R[i]=Carry%Base;  
         Carry/=Base;  
     }  
     R.Len=i;  
     return R;  
}

ostream &operator<<(ostream &Out,const BigInt &V){  
     int i;  
     Out<<(V.Len==0 ? 0:V[V.Len-1]);  
     for(i=V.Len-2;i>=0;i--) for(int j=Base/10;j>0;j/=10) Out<<V[i]/j%10;  
     return Out;  
}

BigInt ans[300];

int main()
{
    ans[0]=1;
    ans[1]=1;
    int i;
    for ( i = 2  ; i <= 250 ; i ++ )
    {
        ans[i]=ans[i-2]+ans[i-1]+ans[i-2];
    }
    int n ;
    while ( cin >> n )
        cout<<ans[n]<<endl;
    return 0;
}

展开全文 >>

poj2663 Tri Tiling 解题报告

9月 14

题目地址：http://poj.org/problem?id=2663

递推题，推导有点复杂，可能还有更好的办法吧，下面是我的想法

用$f_n$表示铺成$3 \times n$没铺满，还有一个空缺，$g_n$表示铺成$3 \times n$没铺满，有两个空缺，用$a_n$表示铺成$3 \times n$时全部铺满。

则很容易知道如果要铺成$a_n$，只需要$g_n$再加一块或者$f_{n-1}$再加两块，故$a_n=g_n+f_{n-1}$

同理，可知只要$f_{n-1}$再加一块就是$g_n$，而$f_n$则是只需要$a_{n-1}$再加一块或者$g_{n-1}$上加（需要点空间想像），综上，就可以推出递推公式了

poj2663 Tri Tilingview raw

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
int a[35];
int f[35];
int g[35];
int main()
{
	int n;
	a[0]=1;
	int i;
	for(i=1;i<31;i++)
	{
		f[i]=2*a[i-1]+g[i-1];
		g[i]=f[i-1];
		a[i]=f[i-1]+a[i-2];
	}
	while(scanf("%d",&n),n+1)
		printf("%d\n",a[n]);
}

展开全文 >>

POJ 2773 互素问题

9月 14

题目大意就是给出n和k求出第k个与n互素的数

如果知道欧几里德算法的话就应该知道gcd（b×t+a，b）=gcd（a，b）（t为任意整数）

则如果a与b互素，则b×t+a与b也一定互素，如果a与b不互素，则b×t+a与b也一定不互素

故与m互素的数对m取模具有周期性，则根据这个方法我们就可以很快的求出第k个与m互素的数

假设小于m的数且与m互素的数有k个，其中第i个是ai，则第m×k+i与m互素的数是k×m+ai

这道题这样做并不是最优的，网上说可以用欧拉函数+容斥原理+二分枚举可做，我暂时还不知道这样做的思想

如果用我的方法做的话，时间上的花费比较大

poj2773 Happy 2006view raw

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
usingnamespace std;
int pri[1000000];
int gcd ( int a , int b ) 
{
    return b ==0? a : gcd ( b , a % b ) ;
}
int main()
{
    int m , k ;
    while ( cin >> m >> k ) 
    {
        int i , j ;
        for ( i =1 , j =0 ; i <= m ; i ++ )
            if ( gcd ( m , i ) ==1 )
                pri [ j ++ ] = i ;

        if ( k%j !=0)
            cout <<k/j * m +pri[k%j-1] << endl;
        else//要特别考虑k%j=0的情况，因为数组是从0开始的，第i个对应的是pri[i-1]
            cout << (k/j-1)*m+pri[j-1] << endl ;
    }
    return0;
}

展开全文 >>

poj 2891 Strange Way to Express Integers 扩展欧几里得

9月 14

题目大意就是给出$a$和$r$，求$c$,其中$c \bmod a_i = r_i$ 这题就是扩展欧几里得的一个简单应用

首先我们可以假设$c=a_0x+r_0=a_1y+r_1$则$a_0x-a_1y=r_1-r_0$;此时可以求出$x$，故可以求出$c$。

假设$A= \mathrm{lcm} (a_0,a_1)$,则$A=a_0t_1=a_1t_1$；那么可以推出$C’=Az+C=a_0tz+a_0x+r_0=a_0(t_0z+x)+r_0=a_1(t_1z+y)+r_1$

故这时再将这两个式子合并写成$C’= \mathrm{lcm} (a_0,a_1)z+C$再与接下来的$a_i$和$r_i$合并即可

poj2891 Strange Way to Express Integersview raw

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))

void e_gcd ( __int64 a , __int64 b , __int64 &d , __int64 &x , __int64 &y )
{

	if ( ! b )
		d = a , x =1 , y =0 ;
	else
		e_gcd ( b , a%b , d , y , x ) , y -= x * ( a / b ) ;
}
__int64 gcd(__int64 a,__int64 b)
{
	return b==0?a:gcd(b,a%b);
}
__int64 lcm(__int64 a,__int64 b)
{
	return a/gcd(a,b)*b;
}
int main()
{
	int T;
	while(~scanf("%d",&T))
	{
		int i,j;
		T--;
		__int64 m,n,r1,r2;
		bool ans=true;
		scanf("%I64d%I64d",&m,&r1);
		for(i=0;i<T;i++)
		{
			scanf("%I64d%I64d",&n,&r2);
			if(ans)
			{
				__int64 x,y,d;
				e_gcd(m,n,d,x,y);
				if((r2-r1)%d!=0)
					ans=false;
				__int64 t=(r2-r1)/d;
				x=x*t;
				y=y*t;
				x%=(n/d);//求出最小正整数x
				while(x<0)
					x+=(n/d);
				r1=m*x+r1;//合并
				m=lcm(m,n);
				if((r1-r2)%n!=0)
					ans=false;
			}
		}
		if(ans)
			printf("%I64d\n",r1);
		else
			printf("-1\n");

	}
    return 0;
}

展开全文 >>

POJ3009Curling 2.0解题报告

9月 14

题目大意就是给出一个w*h的地图，其中0代表空地，1代表障碍物，2代表起点，3代表终点，每次行动可以走多个方格，每次只能向附近一格不是障碍物的方向行动，直到碰到障碍物才停下来，此时障碍物也会随之消失,如果行动时超出方格的界限或行动次数超过了10则会game over .如果行动时经过3则会win，记下此时行动次数（不是行动的方格数），求最小的行动次数

由于题目给出要在10步内找到最优解，又每次可以向四个方向进行搜索，时间复杂度是O（4^10）=O((2^10)^2)=O(1000^2)=O(1000000)

在搜索时如果发现此时搜索的层次已经大于最优解，则可以回溯，因为继续向下搜也不会再出现更优解。

poj3009 Curling 2.0view raw

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int w,h;
struct prog{
    int map[25][25];//迷宫地图
    int x ;    int y ；//此时的坐标
};
int step;            //最优移动次数，初始时为11
void DFS ( prog tmp , int k )
{
    if(k>=step)        //如果递归层数不小于最优移动次数，就没必要继续搜索
        return ;
    int i , j ;

    if(tmp.x+1<h&&tmp.map[tmp.x+1][tmp.y]!=1)
    {//如果该处下面没越界，并且不是障碍物
        for ( i = 1 ; tmp.x + i < h; i ++ )
        {//从该处深度+1开始，一步步寻找
            if(tmp.map[tmp.x+i][tmp.y]==1)
            {//如果找到某处有障碍物，则从该处开始继续搜索
                prog tmp2=tmp;                //定义一个临时结构体
                tmp2.map[tmp.x+i][tmp.y]=0;    //将该处的障碍物消失
                tmp2.x=tmp.x+i-1;            //位置应为障碍物的上面
                DFS(tmp2,k+1);                //继续搜索
                break;
            }

            if(tmp.map[tmp.x+i][tmp.y]==3)
            {//如果经过了3，即终点
                if(step>k+1)    //看搜索的结果是否比最优解优，如果优，更新step
                    step=k+1;
                return ;
            }
        }
    }

    //下面的搜索原理和上面类似，注释略

    if(tmp.x-1>=0&&tmp.map[tmp.x-1][tmp.y]!=1)
    {//向上
        for ( i = 1 ; tmp.x - i >=0; i ++ )
        {
            if(tmp.map[tmp.x-i][tmp.y]==1)
            {
                prog tmp2=tmp;
                tmp2.map[tmp.x-i][tmp.y]=0;
                tmp2.x=tmp.x-i+1;
                DFS(tmp2,k+1);
                break;
            }

            if(tmp.map[tmp.x-i][tmp.y]==3)
            {
                if(step>k+1)
                    step=k+1;
                return ;
            }
        }
    }

    if(tmp.y+1<w&&tmp.map[tmp.x][tmp.y+1]!=1)
    {//向右
        for ( i = 1 ; tmp.y + i < w; i ++ )
        {

            if(tmp.map[tmp.x][tmp.y+i]==1)
            {
                prog tmp2=tmp;
                tmp2.map[tmp.x][tmp.y+i]=0;
                tmp2.y=tmp.y+i-1;
                DFS(tmp2,k+1);
                break;
            }

            if(tmp.map[tmp.x][tmp.y+i]==3)
            {
                if(step>k+1)
                    step=k+1;
                return ;
            }
        }
    }

    if(tmp.y-1>=0&&tmp.map[tmp.x][tmp.y-1]!=1)
    {//向左
        for ( i = 1 ; tmp.y - i >=0; i ++ )
        {
            if(tmp.map[tmp.x][tmp.y-i]==1)
            {
                prog tmp2=tmp;
                tmp2.map[tmp.x][tmp.y-i]=0;
                tmp2.y=tmp.y-i+1;
                DFS(tmp2,k+1);
                break;
            }
            if(tmp.map[tmp.x][tmp.y-i]==3)
            {
                if(step>k+1)
                    step=k+1;
                return ;
            }

        }
    }

}
int main()
{
    while(cin>>w>>h,w&&h)
    {//输入长高
        prog cur;
        int i , j ;
        memset(cur.map,0,sizeof(cur.map));
        for ( i = 0 ; i < h ; i ++ )
        {
            for ( j = 0 ; j < w ; j ++ )
            {
                cin >> cur.map[i][j];
                if(cur.map[i][j]==2)
                {//记录起点坐标
                    cur.x=i;
                    cur.y=j;
                }
            }
        }
        step=11;//初始化为11
        DFS( cur , 0 );
        if(step==11)//说明没找到解
            cout<<-1<<endl;
        else
            cout<<step<<endl;
    }
    return 0;
}

展开全文 >>

poj3070来体会矩阵的妙用

9月 14

题目大意就是求出斐波那契数列第k项的后四位，如果有前导0就不输出0，但最后一个0必须输出

刚开始的时候就想到了一个关于斐波那契数列的数列的一个公式，准备用那个公式求的，但题目已经提示了用矩阵，就没用那个公式

这一题就要注意到矩阵

的右上角或左下角对应的值正好是第n项的值

故可以通过快速幂来求得斐波那契数列的哦n项，由于数据较大，还要记得要不断的对10000取模

矩阵的快速幂我是直接抄的模板，刚开始时不理解，现在懂了，详情直接看代码

poj3070 Fibonacciview raw

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct prog {
    int a[2][2] ;
    void init(){
        a[0][0]=a[1][0]=a[0][1]=1;
        a[1][1]=0;
    }
};

prog matrixmul ( prog a ,prog b )
{
    int i , j , k ;
    prog c ;
    for ( i = 0 ; i < 2; i ++ )
    {
        for ( j = 0 ; j < 2 ; j ++ )
        {
            c.a[i][j]=0;
            for ( k =0 ; k < 2; k ++ )
                c.a[i][j]+=(a.a[i][k]*b.a[k][j]) ;
            c.a[i][j] %= 10000 ;
        }
    }
    return c ;
}
prog mul (prog s , int k )
{
    prog ans ;
    ans.init();
    while ( k >= 1 )
    {
        if ( k & 1 )
            ans = matrixmul ( ans , s ) ;
        k = k >> 1 ;
        s = matrixmul ( s , s ) ;
    }
    return ans ;
}
int main()
{
    int n ;
    while ( cin >> n , ~ n )
    {
        if ( ! n )
        {
            cout<<0<<endl ;
            continue ;
        }
        prog s ;
        s.init ( ) ;
        s = mul ( s , n - 1 ) ;
        cout << s . a [0][1] % 10000 <<endl;
    }

    return 0;
}

展开全文 >>

poj3090 欧拉函数与法雷级数

9月 14

题目大意先看上图，给出大小为n的图（有（n+1）^2个格点），求出图中可视点的个数，可视点就是在图中从（0，0）看不被遮挡的点，例如（1，1）是可视点，（2，2）不是，因为（2，2）被（1，1）给遮挡了

这一题和poj2478的解法类似，解答方法也相似，点此进入poj2478 又一欧拉公式的运用，这题是求法雷级数的题

然而也不能直接就把poj2478的代码个复制过来

因为对于这一题，并没有要求分子一定比分母小，也就是（5，3）也是题目可视点，但进一步观察发现如果（a，b）是可视点，那么（b，a）也一定是可视点

则我们根据这个规律，我们就可以假设出a < b,则只要求出a < b的格点数，然后再乘以2

但还是会有问题，此题中（1，0），（0，1）也是格点数，但我们在运用欧拉函数时并不考虑0，并且也存在a=b的格点，即（1，1）

还好这样特殊的点并不多，只有三个，我们只需要特殊考虑就行了

刚开始是求欧拉函数没考虑边界大情形，RE了两次，最后发现问题，修正了一下，果然AC了

poj3090 Visible Lattice Pointsview raw

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int phi[1005];
int main()
{
    int i , j ;
    memset ( phi , 0 ,sizeof ( phi ) ) ;
    phi[1]=1;
    for ( i = 2 ; i <1005 ; i ++ )
    {//筛选求phi
        if ( ! phi [i] )
        {
            for ( j = i ; j <1005 ; j += i )
            {
                if ( ! phi [j] )
                    phi [j ] = j ;
                phi [j] = phi [j] / i * ( i - 1 ) ;
            }
        }
    }
    int t ;
    int k = 1 ;
    cin >> t ;
    while ( t-- )
    {
        int n ;
        cin >> n ;
        cout << k << ' ' << n << ' ';
        int sum = 3 ;//特别考虑的三个点，（1，0）（0，1）（1，1）
        for ( i = 2 ; i <= n ; i ++ )
            sum += 2 *(phi [i] );
        cout<<sum<<endl;
        k++;
    }
    return 0;
}

展开全文 >>

POJ3185 The Water Bowls 解题报告

9月 14

题目大意和POJ1222 类似，不过这题更简单，只用枚举第一个开关的状态就行了，题目保证有解，只需要简单的位运算即可，这题也可高斯消元

poj3185 The Water Bowlsview raw

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))

int a[25],b[25];
int main()
{
    while(~scanf("%d",&a[0]))
    {
        b[0]=a[0];
        int i;
        for(i=1;i<20;i++)
        {
            scanf("%d",&a[i]);
            b[i]=a[i];
        }
        int ans=1<<20;
        for(i=0;i<2;i++)
        {
            int cnt=0;
            memcpy(b,a,sizeof(b));
            if(i==1)
            {
                b[0]=!b[0];
                b[1]=!b[1];
                cnt++;
            }
            for(int j=1;j<19;j++)
            {
                if(b[j-1]==1)
                {
                    cnt++;
                    b[j-1]=!b[j-1];
                    b[j]=!b[j];
                    b[j+1]=!b[j+1];
                }
            }
            if(b[19]^b[18]==0)
            {
                if(b[19]==1)
                    cnt++;
                if(ans>cnt)
                    ans=cnt;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

展开全文 >>

poj3233 又见矩阵，不过是等比吗？

9月 14

题目大意很明了，初看是像是就等比数列前n项和，但公比是一个矩阵，能用吗？

我不知道，因为如果是类似等比数列前n项和的好像关于矩阵除法比较难写，中间涉及到逆举证神马的，直接忽略

输入的数据第一行分别是$n,k,m$

代表矩阵的是$n \times n$型，求前$k$项和，结果的每一项对$m$取模

然后就是一个$n \times n$的矩阵。

我做这题时用的是类似二分的方法做的，仔细观察可以发现

$S_k = \sum_{i=1}^{k}A_{i}=(1 + {A_{\frac{k}{2}}}) \sum_{i=1}^{\frac{k}{2}}A_i + A_k = (1 + {A_{\frac{k}{2}}})S_{\frac{k}{2}} + A_k (k为奇数)$
$S_k = \sum_{i=1}^{k}A_{i}=(1 + {A_{\frac{k}{2}}}) \sum_{i=1}^{\frac{k}{2}}A_i= (1 + {A_{\frac{k}{2}}})S_{\frac{k}{2}} (k为偶数)$

故可以用这方法直接推出答案，中间要记得对数取模，以防超int，还要注意$S_1=A$ ；

然后就是写矩阵乘法与加法部分，可直接套模板

poj3233 Matrix Power Seriesview raw

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n , m ;
struct matrix {//矩阵
    int a[30][30];
    void init(  )
    {//初始化
        int i ;
        memset ( a, 0 ,sizeof ( a ) ) ;
        for ( i = 0 ; i < 30 ; i ++ )
            a[i][i] = 1 ;
    }
};
void print ( matrix s )
{//打印一个矩阵
    int i , j ;
    for ( i = 0 ; i < n ; i ++ )
    {
        for ( j = 0 ; j < n ; j ++ )
        {
            if ( j )
                cout<<' ';
            cout<<s.a[i][j]%m;
        }
        cout<<endl;
    }
}
matrix matrixadd ( matrix a , matrix b )
{//矩阵加法，计算时记得要取模，避免超int
    int i , j ;
    matrix c ;
    for ( i = 0 ; i < n ; i ++ )
        for ( j = 0  ; j < n ; j ++ )
            c.a[i][j]=((a.a[i][j]+b.a[i][j])%m);
    return c ;
}
matrix matrixmul ( matrix a , matrix b )
{//矩阵乘法，计算时记得要取模，避免超int
    int i , j , k ;
    matrix c ;
    for ( i = 0 ; i < n ; i ++ )
    {
        for ( j = 0 ; j < n ; j ++ )
        {
            c.a[i][j]=0;
            for ( k = 0 ; k < n ; k ++ )
                c.a[i][j] +=((a.a[i][k]*b.a[k][j])%m) ;
            c.a[i][j] %= m ;
        }
    }
    return c ;
}
matrix mul ( matrix s , int k  )
{//矩阵的k次方，快速幂
    matrix ans ;
    ans .init () ;
    while ( k >= 1 )
    {
        if ( k & 1 )
            ans = matrixmul ( ans , s ) ;
        k = k >> 1 ;
        s = matrixmul ( s , s ) ;
    }
    return ans ;
}
matrix sum ( matrix s , int k )
{//举证前k项求和
    if ( k == 1 )
        return s ;
    matrix tmp ;//用来保存答案
    tmp.init();//初始化
    tmp = matrixadd ( tmp , mul ( s , k >> 1 ) );    //计算1+A^(k/2)
    tmp = matrixmul ( tmp , sum ( s , k >> 1 ) ) ;    //计算(1+A^(k/2))*(A + A^2 + A^3 + … + A^(k/2)  )
    if ( k&1 )//考虑是否要+A^k
        tmp = matrixadd ( tmp , mul ( s , k ) ) ;
    return tmp ;//返回前n项的值
}

int main()
{
    int k ;
    while ( cin >> n >> k >> m )
    {
        int i , j ;
        matrix s ;
        for ( i = 0 ; i < n ; i ++ )
            for ( j = 0 ; j < n ; j ++ )
                cin >> s.a[i][j] ;
        s = sum ( s , k ) ;
        print(s);    
    }
    return 0;
}

展开全文 >>

POJ3278 Catch That Cow 解题报告

9月 14

题目大意，就是给出a和b点的横坐标，求到a，b的最小行动次数，其中每次行动只能是下面两种情况之一

向左或向右移动一步，即横坐标加1或者减1
横坐标变成原来的两倍

对于题目给出的数据5 17 ，可以这样进行行动 5 – 10 – 9 – 18 – 17 所以只需要四步就可以到达b

这题因为是求最小行动次数，故可以用BFS，调用STL里面的队列来实现。每次去队首元素，如果到达了b点，输出步子并结束搜索，否则，行动步子+1，并分别将改点的横坐标+1，-1，×2操作后压入队列，一直到寻找到解。注意到当位置的横坐标超过了b点就应该再向右走，故此时应该对其横坐标只有-1操作，还要注意到横坐标为0的特殊情况，此处应该只进行+1行走

刚开始的时候把标记数组开小了，没注意到×2可能会出现超过100,000的情况，提交时RE了一次，把数组改打就AC了

poj3278 Catch That Cowview raw

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
bool hash[400001];    //标记改点是否走过，如果为true则走过
int main()
{
    int m , n ;
    while(cin>> n >> m )
    {
        memset(hash,false,sizeof(hash));//初始化
        pair<int ,int>p;                //第一个代表横坐标，第二个代表走的步子
        p.first=n;
        p.second=0;                        //初始化p
        hash[n]=true;
        queue<pair<int ,int>>bfs;
        bfs.push(p);
        while(!bfs.empty())
        {
            p=bfs.front();        //取队首元素

            if(p.first==m)
            {//此时说明找到了，则输出，并结束搜索
                cout<<p.second<<endl;
                break;
            }

            p.second++;                    //移动次数+1
            pair<int ,int>q;            

            if(p.first<m)
            {//如果改点在目标点的左边
                q=p;
                q.first*=2;                //×2操作
                if(hash[q.first]==false&&q.first)
                {//点没访问过，则从改点开始继续搜索
                    hash[q.first]=true;
                    bfs.push(q);
                }

            //下面搜索同上，注释略
                q=p;
                q.first+=1;                
                if(hash[q.first]==false)
                {
                    hash[q.first]=true;
                    bfs.push(q);
                }

            }

            if(p.first>0)
            {
                q=p;
                q.first--;
                if(hash[q.first]==false)
                {
                    hash[q.first]=true;
                    bfs.push(q);
                }
            }
            bfs.pop();    //队首元素出队列
        }
    }
    return 0;
}

展开全文 >>