首页 > 代码库 > CSU 1511: 残缺的棋盘（BFS啊 ）
CSU 1511: 残缺的棋盘（BFS啊 ）
题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1511
Description
Input
输入包含不超过10000 组数据。每组数据包含6个整数r1, c1, r2, c2, r3, c3 (1<=r1, c1, r2, c2, r3, c3<=8). 三个格子A, B, C保证各不相同。
Output
对于每组数据，输出测试点编号和最少步数。
Sample Input
1 1 8 7 5 6
1 1 3 3 2 2Sample Output
Case 1: 7
Case 2: 3HINT
Source
湖南省第十届大学生计算机程序设计竞赛
代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#define M 10
using namespace std;
int xk,yk;
struct node
{
int x,y;
int step;
};
int xx[8]= {0,1,1,1,0,-1,-1,-1};
int yy[8]= {1,1,0,-1,-1,-1,0,1};
bool visit[M][M];
int n,ansx,ansy;
queue<node>q;
int BFS(int x,int y)
{
if(x==ansx&&y==ansy)
return 0;
int dx, dy;
node front,rear;
front.x=x,front.y=y,front.step=0;
q.push(front);
visit[x][y]=true;
while(!q.empty())
{
front=q.front();
q.pop();
for(int i = 0; i < 8; i++)
{
dx=front.x+xx[i],dy=front.y+yy[i];
if(dx>0&&dx<=n&&dy>0&&dy<=n&&!visit[dx][dy]&&(dx!=xk||dy!=yk))
{
visit[dx][dy]=true;
if(dx==ansx&&dy==ansy)
return front.step+1;
rear.x=dx,rear.y=dy,rear.step=front.step+1;
q.push(rear);
}
}
}
}
int main()
{
int x, y, ans;
int cas = 0;
while(~scanf("%d%d%d%d%d%d",&x,&y,&ansx,&ansy,&xk,&yk))
{
while(!q.empty())
q.pop();
n = 8;
memset(visit,false,sizeof(visit));
ans=BFS(x,y);
printf("Case %d: %d\n",++cas,ans);
}
return 0;
}CSU 1511: 残缺的棋盘（BFS啊 ）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。