P1747 好奇怪的游戏
题目背景
《爱与愁的故事第三弹·shopping》娱乐章。
调调口味来道水题。
题目描述
爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：***（游戏名被打上了马赛克）。这个游戏类似象棋，但是只有黑白马各一匹，在点x1,y1和x2,y2上。它们得从点x1,y1和x2,y2走到1,1。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在爱与愁大神想知道两匹马到1,1的最少步数，你能帮他解决这个问题么？
输入输出格式
输入格式：
第1行：两个整数x1，y1
第2行：两个整数x2，y2
输出格式：
第1行：黑马到1,1的距离
第2行：白马到1,1的距离
输入输出样例
说明
100%数据：x1,y1,x2,y2<=20
bfs
由于要进行两遍bfs，数组与队列记得要清空！
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 110
using namespace std;
bool vis[N][N];
int x1,y1,x2,y2,nx,ny,ans,dis[N][N];
]={,,,,,,-,-,-,-,-,-};
]={-,,-,-,,,-,,-,,-,};
int read()
{
,f=; char ch=getchar();
;ch=getchar();}
+ch-',ch=getchar();
return x*f;
}
struct Node
{
int x,y;
}node,p;
queue<Node>q;
void bfs(int x,int y)
{
while(!q.empty()) q.pop();
memset(vis,,sizeof(vis));
memset(dis,,sizeof(dis));
node.x=x,node.y=y;dis[x][y]=;
q.push(node);vis[x][y]=true;
while(!q.empty())
{
p=q.front();q.pop();
x=p.x,y=p.y;
&&y==) {ans=dis[x][y];return ;}
;i<;i++)
{
nx=x+xx[i],ny=y+yy[i];
||ny>||nx<||ny<||vis[nx][ny]) continue;
vis[nx][ny]=true;
dis[nx][ny]=dis[x][y]+;
p.x=nx,p.y=ny,q.push(p);
}
}
}
int main()
{
x1=read(),y1=read();
bfs(x1,y1);printf("%d\n",ans);
x2=read(),y2=read();
bfs(x2,y2);printf("%d",ans);
;
}