最少步数

题目链接：http://acm.ocrosoft.com/problem.php?cid=1615&pid=19

题目描述

在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100*100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点可能的最少步数。

输入

共两行，每行两个整数，

第一行A点的位置，第二行为B点的位置

输出

为两行，第一行为A点到（1,1）的最少步数，第二行为B点到（1,1）的最小步数

样例输入

12 16

18 10

样例输出

8

9

思路：就是很纯粹的BFS，用一个数组记录一下走的方式，用queue来实现搜索

代码：

#include<bits/stdc++.h>

using namespace std;

struct node

{

    int x,y,step;

    node(){}

    node(int x1,int y1,int step1):x(x1),y(y1),step(step1){}

 

};

const int N=150;

int u[12][2]={{1,2},{1,-2},{-1,2},{-1,-2},{-2,-1},{-2,1},{2,1},{2,-1},{2,2},{-2,-2},{2,-2},{-2,2}};//用数组去记录行走的方式

int vis[N][N];

int a,b,c,d;

void bfs(int x,int y)

{

    memset(vis,0,sizeof(vis));//初始化

    vis[x][y]=1;

    queue<node>Q;//建立队列

    Q.push(node(x,y,0));//入队

    while(!Q.empty())

    {

        node a=Q.front();//取出队首

        Q.pop();

        for(int i=0;i<12;i++){//遍历12种行走方式

            int xx=a.x+u[i][0];

            int yy=a.y+u[i][1];

            if(xx>=1&&xx<=100&&yy>=1&&yy<=100&&(vis[xx][yy]==0)){//如果此时的位置还在迷宫内就进去

                vis[xx][yy]=1;

                Q.push(node(xx,yy,a.step+1));

                if(xx==1&&yy==1){

                    cout<<a.step+1<<endl;//到终点了输出答案

                    return;

                }

            }

        }

    }

 

}

int main()

{

    cin>>a>>b>>c>>d;

    bfs(a,b);//2个初始位置的BFS

    bfs(c,d);

    return 0;

}