【NOJ1043】【算法实验三】【BFS_分支限界】跳马

1043.跳马

时限：1000ms 内存限制：10000K  总时限：3000ms

描述

在国际象棋中，马的走法与中车象棋类似，即俗话说的“马走日”，下图所示即国际象棋中马（K）在一步能到达的格子（其中黑色的格子是能到达的位置）。

现有一200*200大小的国际象棋棋盘，棋盘中仅有一个马，给定马的当前位置（S）和目标位置（T），求出马最少需要多少跳才能从当前位置到达目标位置。

输入

本题包含多个测例。输入数据的第一行有一个整数N（1<=N<=1000），表示测例的个数，接下来的每一行有四个以空格分隔的整数，分别表示马当前位置及目标位置的横、纵坐标C（x,y）和G（x,y）。坐标由1开始。

输出

对于每个测例，在单独的一行内输出一个整数，即马从当前位置跳到目标位置最少的跳数。

第二版代码： 

#include <iostream>
#include <queue>

using namespace std;

//注：题中坐标从【1，1】开始
//然而本代码中坐标从【0，0】开始
//因此题中给的数据sx，sy，tx，ty都做了-1处理

int n;
int sx,sy;
int tx,ty;

int used[200][200];
int step[200][200];

int walk[8][2]=
{
    +1,-2,  //方向1
    +2,-1,  //方向2
    +2,+1,  //方向3
    +1,+2,  //方向4
    -1,+2,  //方向5
    -2,+1,  //方向6
    -2,-1,  //方向7
    -1,-2   //方向8
};

struct node
{
    int hx; //马的当前位置
    int hy;
};

node start,target;

queue <node> q1;

void init();    //初始化

int bfs();

node moveto(node now, int i);   //返回向i方向走一步后得到的新节点

bool effective(node next);      //判断节点next是否有效
                                //无效条件：越界、重复

bool isTarget(node next);       //判断节点next是否到达目标节点


int main()
{
    cin>>n;
    while(n--)
    {
        cin>>sx>>sy>>tx>>ty;

        init();   //初始化

        cout<<bfs()<<endl;
    }
    return 0;
}

void init()     //初始化
{
    for(int i=0; i<200; i++)
    {
        for(int j=0; j<200; j++)
        {
            used[i][j]=step[i][j]=0;
        }
    }

    while(!q1.empty())
    {
        q1.pop();
    }

    start.hx=sx-1;  //坐标-1处理
    start.hy=sy-1;
    used[start.hx][start.hy]=1;
    q1.push(start);

    target.hx=tx-1;
    target.hy=ty-1;
}

int bfs()
{
    node now,next;
    while(!q1.empty())
    {
        now=q1.front();
        q1.pop();

        for(int i=0; i<8; i++)  //向8个方向扩展
        {
            next=moveto(now, i);    //获得新节点next

            if(effective(next))     //若新节点next有效
            {
                used[next.hx][next.hy]=1;   //标记
                step[next.hx][next.hy]=step[now.hx][now.hy]+1;  //步数

                if(isTarget(next))  //若新节点next到达了目标节点
                {
                    return step[next.hx][next.hy];  //返回其步数
                }
                else    //若未到达目标节点，则入队
                {
                    q1.push(next);
                }
            }
        }
    }
    return -1;
}

//返回向i方向走一步后得到的新节点
node moveto(node now, int i)
{
    node next;
    next.hx=now.hx+walk[i][0];
    next.hy=now.hy+walk[i][1];

    return next;
}

//判断节点next是否有效
//无效条件：越界、重复
bool effective(node next)
{
    if(next.hx>=0&&next.hx<200&&next.hy>=0&&next.hy<200)    //不越界
    {
        if(!used[next.hx][next.hy])     //不重复
        {
            return true;
        }
    }
    return false;
}

//判断节点next是否到达目标节点
bool isTarget(node next)
{
    if(next.hx==target.hx&&next.hy==target.hy)
    {
        return true;
    }
    else
    {
        return false;
    }
}

【10月21日后记】

1.刚刚重写了【电子老鼠走迷宫】那道题，但觉得代码结构不太好，重写这道题的时候就注意了一下，目前还是挺满意这种函数设置和代码结构的。

main的主结构只有：init函数，bfs函数，看起来比较简洁；

最重要的函数当然是bfs，但是又新增了几个函数：moveto，effective，isTarget，个人还挺喜欢这几个函数的，既能简化bfs函数，又不过于冗杂。

2.虽然没有一遍过，但只有一个小失误，walk数组有一个元素写错了

3.发现写了新代码之后，与旧代码对比，是一种凌迟酷刑……

【10月7日后记（第一版代码，因为过于羞耻已经删除，但保留后记作为回忆）】

1.写的第一个广搜，吭哧了一上午，主要卡在：

（1）坐标从[1, 1]开始，想当然的把格子也从1开始编号，结果坐标[200, 200]变成[40000]号又变成坐标[201, 0]，出了bug，然后还是用回熟悉的从[0, 0]坐标开始，从0号开始编号；

（2）初始化忘记清空队列

2.用了一个moveto函数，当可以moveto的时候返回的是将要入队的格子序号（>=0），如果判断不能moveto，返回-1