"马走日"问题,BFS解决,比较简单,状态即为当前所在的位置,代码如下:
Code
1
#include <iostream>
2#include <string>
3#include <queue>
4using namespace std;
5
6const int CHESS_SIZE = 8;
7
8struct Position
9
{
10
Position(int x, int y)
11 : X(x), Y(y)
12
{}
13 int X;
14 int Y;
15
16 bool operator==(const Position & position) const
17 {
18 return X == position.X && Y == position.Y;
19
}
20
};
21
22struct
23{
24 int x;
25 int y;
26}dir[8] =
27{
28 {-2, 1},{-1, 2},{1, 2},{2, 1},
29 {2, -1},{1, -2},{-1, -2},{-2, -1}
30};
31
32bool IsInside(const int x, const int y)
33{
34 return x >= 0 && x < CHESS_SIZE && y >= 0 && y < CHESS_SIZE;
35}
36
37int _tmain(int argc, _TCHAR* argv[])
38{
39 string start, end;
40 while(cin >> start >> end)
41 {
42 int chess_count[CHESS_SIZE][CHESS_SIZE] = {-1};
43 bool chess_status[CHESS_SIZE][CHESS_SIZE] = {false};
44
45 int start_col = (int)(start[0] - 'a');
46 int start_row = (int)(start[1] - '0' - 1);
47 int end_col = (int)(end[0] - 'a');
48 int end_row = (int)(end[1] - '0' - 1);
49
50 queue<Position> q;
51 q.push(Position(start_row, start_col));
52 Position goal(end_row, end_col);
53 chess_status[start_row][start_col] = true;
54 chess_count[start_row][start_col] = 0;
55
56 Position current_state(0,0), next_state(0,0);
57
58 // if the start is equal to goal
59 if(q.front() == goal)
60 {
61 cout << "To get from " << start << " to " << end << " takes 0 knight moves." << endl;
62 continue;
63 }
64
65 bool isFind = false;
66 Position new_position(0, 0);
67
68 while(!q.empty())
69 {
70 current_state = q.front();
71 q.pop();
72
73 for(int i = 0; i < 8; ++i)
74 {
75 int x = current_state.X + dir[i].x;
76 int y = current_state.Y + dir[i].y;
77 new_position.X = x;
78 new_position.Y = y;
79
80 // for performance concern, when we found the solution, break it,
81 // otherwise it will wait until all pre-solutions are being handled
82 if(new_position == goal)
83 {
84 isFind = true;
85 break;
86 }
87
88 if(IsInside(x, y) && !chess_status[x][y])
89 {
90 q.push(Position(x, y));
91 chess_status[x][y] = true;
92 chess_count[x][y] = chess_count[current_state.X][current_state.Y] + 1;
93 }
94 }
95 if(isFind)
96 break;
97 }
98
99 cout << "To get from " << start << " to " << end <<
100 " takes " << chess_count[current_state.X][current_state.Y] + 1 << " knight moves." << endl;
101 }
102 return 0;
103}
104
105posted on 2009-03-26 21:17
肖羽思 阅读(1286)
评论(1) 编辑 收藏 引用 所属分类:
ZOJ