迷宫问题

问题描述:迷宫由m行n列的单元格组成,每个单元格要么是空地,要么是障碍物,请你找出一条从起点到终点的最小路径长度

DFS深搜解决迷宫问题

DFS深搜要点：

  1. 使用递归方式求解：先判断当前点是否为终点，非终点时递归调用DFS
  2. 调用DFS前当前点标记为已访问，DFS执行结束后当前点标记为未访问：前者防止递归调用时重复访问当前点走回头路，后者是为探索其他路径时能重复访问该点。
  3. 使用外部变量统计最小步数

代码:

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
#include<stdio.h>
int min = 999999;
int p, q,m,n;//p,q分别表示终点的行坐标和列坐标。 m，n表示该迷宫的函数和列数
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int a[100][100];//1表示空地，2表示障碍物
int v[100][100];//0表示未访问，1表示访问
int startx, starty;//起始位置



void dfs(int x, int y, int step) {
	if (x == p && y == q) {
		
		min = step<min?step:min;
		return;

	}
	//顺时针试探（右下左上）
	for (int k = 0; k <= 3; k++) {
		int tx, ty;
		tx = x + dx[k];
		ty = y + dy[k];
		if (a[tx][ty] == 1 && v[tx][ty] == 0) {
			v[tx][ty] = 1;
			dfs(tx, ty, step + 1);
			v[tx][ty] == 0;

		}
		 
	}
	return;
}
int main() {
	scanf_s("%d%d", &m, &n);
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			scanf_s("%d", &a[i][j]);
		}
	}
	scanf_s("%d%d%d%d", &startx, &starty, &p, &q);
	v[startx][starty] = 1;
	dfs(startx, starty, 0);
	printf("%d", min);
	return 0;
	5 4
	1 1 2 1
	1 1 1 1
	1 1 2 1 //测试数据
	1 2 1 1
	1 1 1 2
	1 1 4 3
				
}

BFS广搜解决迷宫问题

求解思路:

将队首结点可扩展的点入队,如果没有可扩展的点,将队首结点出队.重复以上步骤,直到到达目标位置或者队列为空.BFS搜索到的结果一定是最短的.BFS运用到了队列.

代码:

#include<iostream>
#include<queue>
using namespace std;
int a[100][100];
int v[100][100];
int dx[4] = {0,1,0,-1};
int dy[4] = { 1,0,-1,0 };
struct point {
    int x;
    int y;
    int step;
};
queue<point> r;//申请队列
int main() {
    int n,m,startx, starty, p, q;
    scanf_s("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf_s("%d", &a[i][j]);
        }

    }
    scanf_s("%d%d%d%d", &startx, &starty, &p, &q);
    point start;
    start.x = startx;
    start.y = starty;
    start.step = 0;
    r.push(start);//将起点入队
    v[startx][starty] = 1;
    int flag = 0;
    while (!r.empty()) {	
        int x = r.front().x, y = r.front().y;
        if (x == p && y == q) {
            flag = 1;
            printf("%d", r.front().step);
            break;
        }

        for (int k = 0; k <= 3; k++) {
            int tx, ty;
            tx = x + dx[k];
            ty = y + dy[k];
            if (a[tx][ty] == 1 && v[tx][ty] == 0) {
                //入队
                point temp;
                temp.x = tx;
                temp.y = ty;
                temp.step = r.front().step + 1;
                r.push(temp);
                v[tx][ty] = 1;

            }
        }
        r.pop();//扩展完了需要将队首元素出队
    }	
    if (flag == 0) printf("no ans");
    return 0;
}