暑假训练赛5--Problem B/zcmu1639: 残缺的棋盘
程序员文章站
2023-12-24 12:13:03
...
Problem B: 残缺的棋盘
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 157 Solved: 58
[Submit][Status][Web Board]
Description
在国际象棋里,王是最重要的一个棋子。每一步,王可以往上下左右或者对角线方向移动一
步,如下图所示。
给定两个格子 A(r1,c1), B(r2,c2),你的任务是计算出一个王从 A 到 B 至少需要走多少步。为了
避免题目太简单,我们从棋盘里拿掉了一个格子 C(r3,c3)(ABC 保证互不相同),要求王从 A
走到 B 的过程中不能进入格子 C。在本题中,各行从上到下编号为 1~8,各列从左到右编号为
1~8。
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 2
Sample Output
Case 1: 7
Case 2: 3
【分析】
- 用到队列,然后结构体;
- 为什么不用栈呢?因为栈常用来解决dfs,而队列是bfs;显然该题是广度优先搜索,即先把附近的一圈找完然后再扩展;
- bfs模板
初始化队列Q Q={起点s}; 标记s已被访问; while(Q非空){ 去Q的队首元素u; u出队2; if(u==目标状态){...} 所有的与u相邻且未被访问的点进入队列; 标记u已被访问; }
- 注意要把走过的标记,还要判断是否超出边界;
- 注意每次结束后清空队列!!!!!!!
- 一开始有想过题目是要求最短路径,可是怎么比较呢。但是,广度优先搜索,一圈一圈来,所以在这一圈中走的步数是一样的,知道这一圈中目标位置出现,那么久不用走了,并且该路径必然是最短路径。
- 通过把队列的首元素赋给head,可以保存刚入队的元素的对应x,y,step值,并且赋值完成后就弹出,不会影响到下一次的循环。
【代码】
#include<bits/stdc++.h>
using namespace std;
//定义一个数组来记录该元素是否走过,尽量大一点 吧
int a[201][201];
//定义数组,存储8个方向,bfs遍历时用
int next[8][2]={{1,0},{-1,0},{0,1},{-1,1},{-1,-1},{0,-1},{1,-1},{1,1}};//顺序不影响结果
//定义结构体,保存横纵坐标以及走的步数
struct node{
int x;
int y;
int step;
}head,tail;
//定义队列,node型
queue<node> q;
int main()
{
int r1,c1,r2,c2,r3,c3,j=1;
while(~scanf("%d%d%d%d%d%d",&r1,&c1,&r2,&c2,&r3,&c3))
{
while(!q.empty())q.pop();//注意每次要清空队列!!!!!!!!!
memset(a,0,sizeof(a));
head.x=r1;
head.y=c1;
head.step=0;
q.push(head);
while(!q.empty())
{
head=q.front();//使head始终表示队首元素
q.pop();//每次其实队列中到这一步只有一个元素,在上一步以及赋值给head,
//在此就是清空队列了;
if(head.x==r2&&head.y==c2)
{
printf("Case %d: %d\n",j++,head.step);
break;
}
for(int i=0;i<8;i++)
{
tail.x=head.x+next[i][0];
tail.y=head.y+next[i][1];
if(tail.x<1||tail.y<1||tail.x>8||tail.y>8)continue;
if(tail.x==r3&&tail.y==c3)continue;
if(a[tail.x][tail.y])continue;
tail.step=head.step+1;
a[tail.x][tail.y]=1;
q.push(tail);
//cout<<tail.step<<endl;
}
}
}
return 0;
}