首页 > POJ解题报告 > POJ 1915 Knight Moves[BFS]

POJ 1915 Knight Moves[BFS]

Knight问题,这个题比较好,给了个图说明了Knight的运行规则。这类题一般都是BFS做啦,可以定义一个数组存放移动的方法,这样更加方便。
更多题目:
POJ 1915 Knight Moves http://poj.org/problem?id=1915
POJ 2243 Knight Moves http://poj.org/problem?id=2243
POJ 2488 A Knight’s Journey http://poj.org/problem?id=2488

解题代码:

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
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
 
typedef struct _S_NODE
{
	int x, y;
	int step;
} Node;
 
int size = 0;
bool flag[310][310];
 
int step[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, 
{2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
 
bool CheckValid(const Node& node)
{
	if (node.x >= 0 && node.x < size 
		&& node.y >= 0 && node.y < size
		&& !flag[node.x][node.y])
	{
		return true;
	}
	return false;
}
 
int BFS(const Node& s, const Node& e)
{
	queue<Node> q;
	q.push(s);
	memset(flag, 0, sizeof(flag));
	while (!q.empty())
	{
		Node tmp = q.front();
		q.pop();
		if (tmp.x == e.x && tmp.y == e.y)
		{
			return tmp.step;
		}
 
		for (int i = 0; i < 8; ++i)
		{
			Node node = tmp;
			node.x += step[i][0];
			node.y += step[i][1];
			++node.step;
			if (CheckValid(node))
			{
				q.push(node);
				flag[node.x][node.y] = 1;
			}
		}
	}
	return 0;
}
 
int main(int argc, char **argv)
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
 
	int n;
	scanf ("%d", &n);
	while (n--)
	{
		scanf ("%d", &size);
		Node start, end;
		scanf ("%d %d", &start.x, &start.y);
		scanf ("%d %d", &end.x, &end.y);
		start.step = end.step = 0;
		printf ("%d\n", BFS(start, end));
	}
 
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> POJ 1915 Knight Moves[BFS]
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



分类: POJ解题报告 标签: ,
  1. 本文目前尚无任何评论.