【CSU-1224】解题报告（BFS，水题，2018暑选入门A题）

原始题目

1224: ACM小组的古怪象棋

Time Limit: 1 Sec
Memory Limit: 128 Mb
Submitted: 851
Solved: 347

Description

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

Input

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

Output

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

Sample Input

8 8 5 1 4 5

Sample Output

3

Hint

Source

CSU Monthly 2011 Dec.

题目大意

如题 # 解题思路

马的坐标为单入口BFS，如果搜索不到输出-1.

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define maxn 35
using namespace std; 
int n,m,x1,y1,x2,y2;

bool vis[maxn][maxn];
int dir[8][2]={{-2,1},{-2,-1},{-1,2},{-1,-2},{1,2},{1,-2},{2,1},{2,-1}};
struct State // BFS 队列中的状态数据结构
{
	int x,y;
	int Step_Counter; // 搜索步数统计器
};

//State a[maxn];
int ans[maxn];

bool CheckState(State next) // 约束条件检验
{
	if(next.x>=1&&next.x<=n&&next.y>=1&&next.y<=m&&!vis[next.x][next.y]) // 满足条件	
	{
//		printf("next x=%d y=%d\n",next.x,next.y);
		return 1;
	}	
	else // 约束条件冲突
		return 0;
}

void bfs(State st)
{
	int flag=0;
	queue <State> q; // BFS 队列
	State now,next; // 定义2个状态，当前和下一个
	st.Step_Counter=0; // 计数器清零
	q.push(st); // 入队	
	vis[st.x][st.y]=1; // 访问标记
	while(!q.empty())
	{
		now=q.front(); // 取队首元素进行扩展
//		a[now.i].Step_Counter=++circle;
		if(now.x==x1&&now.y==y1) 
		{
			flag=1;
			printf("%d\n",now.Step_Counter);
			return ;
		}
	
		for(int i=0;i<8;i++)
		{
			next.x=now.x+dir[i][0];
			next.y=now.y+dir[i][1]; 
			next.Step_Counter=now.Step_Counter+1; // 计数器加1
			if(CheckState(next)) // 如果状态满足约束条件则入队
			{
				q.push(next);
//				printf("insert x=%d y=%d\n",next.x,next.y);
				vis[next.x][next.y]=1; //访问标记
			}
		}
		q.pop(); // 队首元素出队
	}
	printf("-1\n");
 	return;
}

int main()
{
	while(~scanf("%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2))
	{
		memset(vis,0,sizeof(vis));
		State start;
		start.x=x2;
		start.y=y2;
		bfs(start);

	}
	return 0;
}

收获与反思

bfs，可以考虑将模板改为bool型。