【题目描述】

一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。

给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。

【输入描述】

第一行是两个整数，R和C，代表迷宫的行数和列数。（ 1<= R，C <= 40)

接下来是R行，每行C个字符，代表整个迷宫。空地格子用’.‘表示，有障碍物的格子用’#‘表示。迷宫左上角和右下角都是’.’。

【输出描述】

【样例输入】

5 5
..###
#....
#.#.#
#.#.#
#.#..

【样例输出】

9

【题目分析】

BFS样例题目

80分版本（超时）

#include<bits/stdc++.h>
using namespace std;
char Map[45][45];
int dir[4][2]={1,0,-1,0,0,-1,0,1};
int n,m,ans;
struct node{
	int x,y,step;
}now,nextt;
queue<node> q;
int BFS(int x,int y){
	int xx,yy,zz;
	Map[x][y]='6';
	now.x=x;
	now.y=y;
	now.step=0;
	q.push(now);
	while(!q.empty()){
		now=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			xx=now.x+dir[i][0];
			yy=now.y+dir[i][1];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&Map[xx][yy]!='#'&&Map[xx][yy]!='6'){
				nextt.x=xx;
				nextt.y=yy;
				nextt.step=now.step+1;
				Map[now.x][now.y]='6';
				if(Map[xx][yy]=='9'){
					return nextt.step;
				}
				q.push(nextt);
			}
		}
	}
	return -1;
}
int main(){
    cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>Map[i][j];
		}
	}
	Map[n][m]='9';
	ans=BFS(1,1);
	cout<<ans+1;
	return 0;
}

100分版本：

#include<bits/stdc++.h>
using namespace std;
char Map[45][45]; // 存储迷宫
bool visited[45][45]; // 记录访问状态
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四个方向
int n, m;
struct node {
    int x, y, step;
}now,nextt;
queue<node> q; //队列 
int BFS(int startX, int startY) {
    now.x=startX;
    now.y=startY;
    now.step=1;
	q.push(now); // 起点步数为 1
    visited[startX][startY] = true; //标记 
    while (!q.empty()) {
        node now = q.front();
        q.pop();
        // 到达终点
        if (now.x == n && now.y == m) {
            return now.step;
        }
        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            int xx = now.x + dir[i][0];
            int yy = now.y + dir[i][1];
            // 检查边界和访问状态
            if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && Map[xx][yy] == '.' && !visited[xx][yy]) {
                visited[xx][yy] = true; // 标记为已访问
                nextt.x=xx;
				nextt.y=yy;
				nextt.step=now.step+1;
				q.push(nextt);
            }
        }
    }
    return -1; // 如果没有找到路径（题目保证一定有路径）
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> Map[i][j];
        }
    }

    // 初始化访问数组
    memset(visited, false, sizeof(visited));

    // 起点是 (1, 1)，终点是 (n, m)
    int ans = BFS(1, 1);
    cout << ans << endl;

    return 0;
}

优化操作：

1. 优化访问标记

在原代码中，使用 Map[xx][yy]='6' 来标记访问过的节点。这种方法会修改地图数据，可能导致不必要的麻烦。建议使用一个独立的二维数组 visited 来记录访问状态。

2. 提前终止

当找到终点时，直接返回结果，避免继续搜索。

3. 减少不必要的操作

在每次循环中，Map[now.x][now.y]='6' 的操作是不必要的，因为当前节点已经在队列中，不需要重复标记。

4. 优化队列操作

使用 queue 时，尽量避免频繁的入队和出队操作。可以通过优化条件判断来减少不必要的入队。