迷宫问题（bfs）
POJ - 3984
1 #include <iostream>
2 #include <queue>
3 #include <stack>
4 #include <cstring>
5
6 using namespace std;
7
8 /*广度优先搜索*/
9 /*将每个未访问过的邻接点进队列，然后出队列，知道到达终点*/
10
11 typedef class
12 {
13 public:
14 int x;
15 int y;
16 }coordinate;
17
18 int maze[5][5]; //迷宫
19 int road[4][2] = { { 0, -1 }, { 1, 0 }, { -1, 0 }, { 0, 1 } };
20 coordinate pre[20][20]; //记录当前坐标的前一个坐标
21
22 int visited[5][5] = { 0 };
23
24 /*利用一个栈，倒序输出pre中存入的坐标*/
25 void print()
26 {
27 stack<coordinate> S;
28 coordinate rhs = { 4, 4 };
29
30 while (1)
31 {
32 S.push(rhs);
33 if (rhs.x == 0 && rhs.y == 0)
34 break;
35 rhs = pre[rhs.x][rhs.y];
36 }
37
38 while (!S.empty())
39 {
40 rhs = S.top();
41 S.pop();
42 cout << "(" << rhs.x << ", " << rhs.y << ")" << endl;
43 }
44 }
45
46 void bfs(int x, int y)
47 {
48 queue<coordinate> Q; //用来帮助广度优先搜索
49 coordinate position;
50
51 position.x = x, position.y = y;
52
53 Q.push(position);
54
55 while (!Q.empty())
56 {
57 position = Q.front();
58 Q.pop();
59
60 visited[position.x][position.y] = 1;
61 coordinate position2;
62
63 if (position.x == 4 && position.y == 4) //如果找到终点，停止搜索
64 {
65 print();
66 return;
67 }
68
69 for (int i = 0; i < 4; i++)
70 {
71
72 position2.x = position.x + road[i][0];
73 position2.y = position.y + road[i][1];
74
75 if (position2.x >= 0 && position2.x <= 4 && position2.y >= 0 && position2.y <= 4 && maze[position2.x][position2.y] == 0 && !visited[position2.x][position2.y]) //如果这个邻接点不是墙且未访问过，则进队列
76 {
77 Q.push(position2);
78 pre[position2.x][position2.y] = position; //记录当前坐标的前一个坐标位置
79 visited[position2.x][position2.y] = 1;
80 }
81
82 }
83 }
84 }
85
86 int main()
87 {
88 memset(maze, 0, sizeof(pre));
89 for (int i = 0; i < 5; i++)
90 for (int j = 0; j < 5; j++)
91 {
92 cin >> maze[i][j];
93 }
94
95 //memset(pre, 0, sizeof(pre)); //现将pre初始化
96
97 bfs(0, 0);
98
99
100 return 0;
101 }
A Knight's Journey
OpenJ_Bailian - 2488
1 #include <cstring>
2 #include<iostream>
3 using namespace std;
4
5 char route[27][2]; //记录行驶的路线
6 int board[9][9]; //棋盘
7
8 int total = 0;
9 int length;
10 /*dfs深度优先搜索*/
11
12 int go[8][2] = { { -1, -2 }, { 1, -2 }, { -2, -1 }, { 2, -1 }, { -2, 1 }, { 2, 1 }, { -1, 2 }, { 1, 2 } };//字典序方向
13
14 /*一次跳跃*/
15 void knight(int p, int q,int len ,int row, int col) //len为行走的距离，用来判断是否遍历整个棋盘, row和col为当前坐标
16 {
17 board[row][col] = 1;
18 route[len][0] = col + 'A' - 1, route[len][1] = row + '0';
19 length = len;
20 /*让马分别尝试8个方向的跳跃，知道跳不动为止*/
21
22 int x, y;
23
24 for (int i = 0; i < 8; i++)
25 {
26
27 x = row + go[i][0];
28 y = col + go[i][1];
29
30 if (x >0 && x <= p && y > 0 && y <= q && board[x][y] == 0)
31 knight(p, q, len + 1, x, y);
32 }
33
34 /*if (row - 1 >= 1 && col - 2 > 0 && board[row - 1][col - 2] == 0)
35 knight(p, q, len + 1, row - 1, col - 2);
36
37 if (row + 1 <= p && col - 2 > 0 && board[row + 1][col - 2] == 0)
38 knight(p, q, len + 1, row + 1, col - 2);
39
40 if (row - 2 >= 1 && col - 1 > 0 && board[row - 2][col - 1] == 0)
41 knight(p, q, len + 1, row - 2, col - 1);
42
43 if (row + 2 <= p && col - 1 > 0 && board[row + 2][col - 1] == 0)
44 knight(p, q, len + 1, row + 2, col - 1);
45
46 if (row - 2 >= 1 && col + 1 <= q && board[row - 2][col + 1] == 0)
47 knight(p, q, len + 1, row - 2, col + 1);
48
49 if (row + 2 <= p && col + 1 <= q && board[row + 2][col + 1] == 0)
50 knight(p, q, len + 1, row + 2, col + 1);
51
52 if (row - 1 >= 1 && col + 2 <= q && board[row - 1][col + 2] == 0)
53 knight(p, q, len + 1, row - 1, col + 2);
54
55 if (row + 1 <= p && col + 2 <= q && board[row + 1][col + 2] == 0)
56 knight(p, q, len + 1, row + 1, col + 2);*/
57
58 }
59
60 int main()
61 {
62 int N, p, q; //行数， 每次的宽和高
63 cin >> N;
64
65 while (N--)
66 {
67 cin >> p >> q;
68 knight(p, q, 0, 1, 1); //以行走了0个单元
69 cout << "Scenario #" << ++total << ":" << endl;
70 if (length == p * q - 1)
71 {
72
73 for (int i = 0; i <= length; i++)
74 cout << route[i][0] << route[i][1];
75 cout << endl << endl;
76 }
77 else
78 cout << "impossible" << endl << endl;
79 memset(board, 0, sizeof(board)); //清空棋盘的足迹
80 memset(route, 0, sizeof(route)); //清空路线
81 }
82
83 return 0;
84 }