队列模拟基本操作I

看到这道题，第一个想法就是“搜索”！“回溯”！的确，这种思路是很正确的，BFS和DFS都可以来解决：

#include <cstdlib>

#include <cstring>

#include <iostream>

using namespace std;

int dx[]= {-,-,-,,,,,,,-,-,-},

            dy[]= {-,-,-,-,-,-,,,,,,};

int main() {

    int s[][],que[][]= {},x1,y1,x2,y2;

    memset(s,0xff,sizeof(s));      //s数组的初始化

    int head=,tail=;                   //初始位置入队

    que[][]=;

    que[][]=;

    que[][]=;

    cin>>x1>>y1>>x2>>y2;         //读入黑马和白马的出发位置

    while(head<=tail) {                  //若队列非空，则扩展队首结点

        for(int d=; d<=; d++) {      //枚举12个扩展方向

            int x=que[head][]+dx[d];  //计算马按d方向跳跃后的位置

            int y=que[head][]+dy[d];

            if(x>&&y>)

                if(s[x][y]==-) {                //若（x,y）满足约束条件

                    s[x][y]=que[head][]+;       //计算(1,1)到(x,y)的最少步数

                    tail++;                //（1,1）至（x,y）的最少步数入队

                    que[tail][]=x;

                    que[tail][]=y;

                    que[tail][]=s[x][y];

                    if(s[x1][y1]>&&s[x2][y2]>) { //输出问题的解

                        cout<<s[x1][y1]<<endl;

                        cout<<s[x2][y2]<<endl;

                        system("pause");

                        return ;

                    }

                }

        }

        head++;

    }

    return ;

}

咱们来模拟以下队列的操作：

首先，初始化一个队列（拿脑子想出了一个队列……），然后，定义头指针head和尾指针tail都为1。

　　如果尾指针在head的位置上或者head的前面，则这个queue不是空的或者这个队列中的元素还没有完全处理完。

　　相反，判断一个队列是否为空或者其中的元素是否全部处理完毕，那就可以用 tail > head 来判断了。

　　当有新的元素加入进来，旧的元素不要就可以tail+1，尾指针向上移一位。

　　当然，你也可以用STL的序列式容器queue，也是根据个人习惯的。

　　但是……

　　这道题有个bug。

　　我们不妨来倒推，它要去(1,1)这个点，我们就从(1,1)这个点去(x,y)这个位置。

　　当我们统计每一个坐标点都能走几步能到达时，得到了这个图：

　　可以看出当行数和列数都小于等于5的时候是没有规律的，但当行数和列数是大于5的时候，是以两个为单位依次递增，也就是第六、第七列是3，第八、第九列是4，第十、第十一是5……然后再在1到5之内特判一下，就可以得到了：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int main()

{

    int x,y,k;

    for(int i=;i<=;i++)

    {

        cin>>x>>y;

        if(x<=&&y<=)

        {

            if((x==&&y>=&&y<=)||(y==&&x>=&&x<=)||(x==&&y>=&&y<=)||(y==&&x>=&&x<=)||x==&&y==||x==&&y==||x==&&y==)

                printf("");

            if(x==&&y==||x==&&y==||x==&&y==)

                printf("");

            if(x==&&(y>=&&y<=)||x==&&y==)

                printf("");

            if(x==&&y==)

                printf("");

        }

        else

        {

            for(int i=,k=;i<=max(x,y);i+=,k++)

            {

                if(max(x,y)==i)

                printf("%d ",k);

            }

        }

    }

    return ;

}

巴特西

队列模拟基本操作I

最新文章

热门文章