【题目描述】

一个迷宫由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 时，尽量避免频繁的入队和出队操作。可以通过优化条件判断来减少不必要的入队。