1224: ACM小组的古怪象棋

Lime Limit: 1 Sec Memory Limit: 128 Mb Submitted: 918 Solved: 382

Description

ACM小组的Samsara和Staginner对中国象棋特别感兴趣，尤其对马（可能是因为这个棋子的走法比较多吧）的使用进行深入研究。今天他们又在构思一个古怪的棋局:假如Samsara只有一个马了，而Staginner又只剩下一个将，两个棋子都在棋盘的一边，马不能出这一半棋盘的范围，另外这一半棋盘的大小很奇特(n行m列)。Samsara想知道他的马最少需要跳几次才能吃掉Staginner的将(我们假定其不会移动)。当然这个光荣的任务就落在了会编程的你的身上了。

Input

每组数据一行，分别为六个用空格分隔开的正整数n,m,x1,y1,x2,y2分别代表棋盘的大小n,m,以及将的坐标和马的坐标。（1<=x1,x2<=n<=20,1<=y1,y2<=m<=20,将和马的坐标不相同）

Output

输出对应也有若干行，请输出最少的移动步数,如果不能吃掉将则输出“-1”(不包括引号)。

Sample Input

8 8 5 1 4 5

Sample Output

3

分析：
就是bfs的水题，需要注意的是先输入的是将的位置。。。。
w了好几次，还有就是注意方向引导数组别写错了，马走的是日字

code：

#include<stdio.h>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <math.h>

#include <cstdlib>

#include <queue>

using namespace std;

#define max_v 25

int dir[][]={{,},{,},{-,},{-,},{-,-},{-,-},{,-},{,-}};

int n,m,sx,sy,fx,fy;

int vis[max_v][max_v];

struct node

{

    int x,y,step;

};

int f(int x,int y)//越界 或 走过

{

    if(x>=&&x<n&&y>=&&y<m&&vis[x][y]==)

    {

        return ;

    }

    return ;

}

int bfs()

{

    queue<node> q;

    node p,next;

    p.x=sx;

    p.y=sy;

    p.step=;

    q.push(p);

    vis[sx][sy]=;

    while(!q.empty())

    {

        p=q.front();

        q.pop();

        if(p.x==fx&&p.y==fy)

        {

            return p.step;

        }

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

        {

            next.x=p.x+dir[i][];

            next.y=p.y+dir[i][];

            if(f(next.x,next.y)==)

            {

                next.step=p.step+;

                vis[next.x][next.y]=;

                q.push(next);

            }

        }

    }

    return -;

}

int main()

{

    while(~scanf("%d %d %d %d %d %d",&n,&m,&fx,&fy,&sx,&sy))

    {

        memset(vis,,sizeof(vis));

        int ans=bfs();

        cout<<ans<<endl;

    }

    return ;

}