案例1：走迷宫
一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地可以走。给定一个迷宫，求从左上角走到右下角最少需要走多少步（数据保证一定能走到）。只能在水平和垂直走，不能斜着走。
输入：R和C代表迷宫的长和宽（1<=R,C<=40）
空地用.表示，障碍物用#表示。迷宫左上角和右下角都为.。
输出：从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。
输入：
5 5
..###
#....
#.#.#
#.#.#
#.#..
输出：9
求解思路：
map[R][C]：.#构成的障碍物图
vis[R][C]：0-1矩阵变量，用于记录地图上的位置是否已经遍历过
arc[4][2]={{0,-1},{-1,0},{0,1},{1,0}}：左上右下情况下横轴和纵轴量的变化情况
用dfs(int row, int col, int step)来进行相应的深度优先遍历，设置深度优先遍历的回溯条件是超出边界（row<0||row>R||col<0||col>C）或者是 已经遍历过vis[row][col]=1 或者是遇到障碍物map[row][col]='#'。
设置深度优先遍历结果比较出口，到达了右下角（row=R && col=C）。
C++代码：
#include<iostream>
#include<limits>
using namespace std;
char map[50][50];
int mina = std::numeric_limits<int>::max();
int R, C;
bool vis[50][50];
int arc[4][2] = { {0,1},{-1,0},{0,1},{1,0} };
void dfs(int row, int col, int step) {
if (row == R && col == C) {
if (mina > step) {
mina = step;
return;
}
}
else {
for (int i = 0; i < 4; i++) {
int x = row + arc[i][0];
int y = col + arc[i][1];
if (x < 0 || x > R || y < 0 || y > C || map[x][y] == '#' || vis[x][y])
continue;
vis[x][y] = 1;
dfs(x, y, step + 1);
vis[x][y] = 0;
}
}
}
int main() {
cin >> R >> C;
R--;
C--;
for (int i = 0; i <= R; i++) {
for (int j = 0; j <= C; j++)
cin >> map[i][j];
}
dfs(0, 0, 1);
cout << mina << endl;
return 0;
}
案例2：走迷宫
有一个nm格的迷宫（表示有n行m列），其中有可走的也有不可走的。如果用1表示可走的，0表示不可走，文件读入这nm个数据点和起始点、终点（起始点和终点都是用两个数据描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可走的道路，要求所有的路中没有重复的点，走时只能上下左右四个去向。如果一条路不可行，则输出相应的信息（用-1表示无路）
输入：第一行是2个数n,m（1<n,m<15），接下来n行m列由1和0组成的数据。最后2行是起始点和结束点
如：
5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6
输出：
(1,1)->(2,1)->(2,2)->...->(5,6)
(1,1)->(2,1)->(2,2)->...->(5,6)
...
求解思路：
此案例相较于案例有两个额外的需求：(1)输出完整的路径序列结果；（2）输出的完整路径序列结果不能有重复的路径点；
int ans[105][2]：用于记录算法中每一步迭代路径点的x和y值；
bool opt[R][C]: 用于判断算法输出的结果的路径点是否重复；
C++代码：
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int map[20][20];
int route[105][2];
int arc[4][2] = { {0,-1}, {-1,0}, {0,1}, {1,0} };
bool opt[20][20];
bool vis[20][20];
int n, m;
int startn, startm;
int endn, endm;
bool is_suc = false;
void dfs(int row, int col, int step) {
if (row == endn && col == endm) {
memset(opt, 0, sizeof(opt));
for (int i = 1; i <= step; i++) {
if (opt[route[i][0]][route[i][1]] == 1) return;
else opt[route[i][0]][route[i][1]] = 1;
}
cout << "(" << route[1][0] << "," << route[1][1] << ")";
for (int i = 2; i <= step; i++) {
cout << "->(" << route[i][0] << "," << route[i][1] << ")";
}
cout << endl;
is_suc = true;
}
else {
for (int i = 0; i < 4; i++) {
int x = row + arc[i][0];
int y = col + arc[i][1];
if (x <= 0 || x > n || y <= 0 || y > m)
continue;
if (map[x][y] == 0 || vis[x][y])
continue;
vis[x][y] = 1;
route[step + 1][0] = x;
route[step + 1][1] = y;
dfs(x, y, step+1);
vis[x][y] = 0;
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
cin >> map[i][j];
}
cin >> startn >> startm;
cin >> endn >> endm;
route[1][0] = startn;
route[1][1] = startm;
dfs(startn, startm, 1);
if (!is_suc)
cout << "-1" << endl;
return 0;
}
案例3：最小开门数
小明家有很大的房子，有很多房间。先输入roomA，然后输入roomB，再输入门的个数N（N<=100）。接着输入N行门，意味着从一个房间（第一个数字，int型）到另一个房间（第二个数字）。请问roomA到roomB最短要经过几个门。
输入：
1
5
5
1 2
2 3
3 4
2 5
4 5
输出： 2
求解思路1：暴力回溯搜索法（会超时）
int A[101]、B[101]：记录这N对门之间的房间号
bool vis[max_Int]： 记录第i个房间是否已经访问
bool arr[max_Int][max_Int]：记录房间之间是否有连接关系
#include<iostream>
#include<cstring>
#include<limits>
#define max_Int 2000
using namespace std;
int ans, roomA, roomB, N;
int A[101], B[101];
bool vis[max_Int]; //记录第i个房间是否已经访问
bool arr[max_Int][max_Int]; //记录房间之间是否有连接关系
void dfs(int cur, int step) { //从cur房间号开始搜索
if (cur == roomB) {
if (step < ans) {
ans = step;
}
return;
}
else {
for (int i = 0; i < N; i++) {
if ((vis[B[i]] == 0) && (arr[cur][B[i]] == 1 || arr[B[i]][cur] == 1)) {
//B[i]没走过，有B[i]到cur的门
vis[B[i]] = 1; //尝试走
dfs(B[i], step + 1);
vis[B[i]] = 0;
}
if ((vis[A[i]] == 0) && (arr[A[i]][cur] == 1 || arr[cur][A[i]] == 1)) {
//A[i]没走过，有A[i]到cur的门
vis[A[i]] = 1;
dfs(A[i], step + 1);
vis[A[i]] = 0;
}
}
}
}
int main() {
while (cin >> roomA >> roomB >> N) {
ans = max_Int;
memset(vis, 0, sizeof(vis));
memset(A, 0, sizeof(A));
memset(B, 0, sizeof(B));
memset(arr, 0, sizeof(arr));
for (int i = 0; i < N; i++) {
cin >> A[i] >> B[i];
arr[A[i]][B[i]] = 1;
arr[B[i]][A[i]] = 1;
}
vis[roomA] = 0;
dfs(roomA, 0);
cout << ans << endl;
}
return 0;
}
求解思路2：广度优先搜索法（successful）
bool arc[205][205]：邻接矩阵，用于存放图中顶点之间的是否可达
bool vis[205]：存放顶点是否已经访问
vector<int>vertex：存放顶点实际编号信息
int que[205]：广度游戏遍历的队列信息
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<stdio.h>
using namespace std;
int froom, eroom, N, roomA, roomB;
int front, rear;
bool arc[205][205]; //邻接矩阵，用于存放图中顶点之间的联系
bool vis[205]; //存放顶点是否已经访问信息
vector<int> vertex; //存放顶点实际编号信息
int que[205]; //广度优先遍历的队列信息
int bfsearch(int fr) {
//从顶点fr进行广度优先遍历
int ans = 0;
int sz = vertex.size();
int v = -1;
int step[205]; //记录走到的步数
memset(step, 0, sizeof(step));
for (int i = 0; i < sz; i++) {
if (vertex[i] == fr) {
v = i;
break;
}
}
if (v == -1)
return -1; //不可走
front = rear = -1;
vis[v] = 1;
que[++rear] = v;
while (front <= rear) {
int i;
v = que[++front]; //出队
for (i = 0; i < sz; i++) {
if (arc[v][i] == 1 && !vis[i]) {
que[++rear] = i;
vis[i] = 1;
step[rear] = step[front] + 1; //单层找到长度+1
if (vertex[i] == eroom) {
return step[rear];
}
}
}
}
}
int main() {
while (cin >> froom >> eroom >> N) {
memset(arc, 0, sizeof(arc));
memset(vis, 0, sizeof(vis));
memset(que, 0, sizeof(que));
vertex.clear();
int ra, rb, shortestDis;
for (int i = 0; i < N; i++) {
cin >> roomA >> roomB;
int sz = vertex.size();
for (ra = 0; ra < sz; ra++) {
if (vertex[ra] == roomA)
break;
}
if (ra == sz) { //roomA不在顶点列表中
vertex.push_back(roomA);
}
sz = vertex.size();
for (rb = 0; rb < sz; rb++) {
if (vertex[rb] == roomB)
break;
}
if (rb == sz) { //roomB不在顶点列表中
vertex.push_back(roomB);
}
arc[ra][rb] = 1;
arc[rb][ra] = 1;
}
shortestDis = bfsearch(froom);
if (shortestDis == -1) {
cout << "找不到" << endl;
}
else {
cout << shortestDis << endl;
}
}
return 0;
}
