作业介绍

#include <iostream>
#include <queue>
using namespace std;

// 队列:先进先出

// 1、能不能从起点走到终点     (枚举、搜索算法)
// 2、从起点到终点有多少种方法 (深度优先搜索DFS)
// 3、从起点到终点的最短路径   (广度优先搜索BFS)

int n,m;   // 地图长宽
int sx,sy, ex,ey;   // 起点  终点
char mp[505][505];  
bool vis[505][505];   // 标记哪些地方已经走过
int dx[4] = {-1, 0, 1, 0};   // 上、右、下、左  
int dy[4] = {0, 1, 0, -1};

// 横纵坐标、步数
struct Node{
	int x,y,step;
};

int bfs(int sx, int sy){
	queue<Node> q;  // 维护要搜索的格子信息
	Node t = {sx, sy, 1};
	q.push(t);      // 起点入队
	vis[sx][sy] = 1; // 标记起点被搜索过了
	// 开始搜索
	while(!q.empty()){
		// 获取队首元素进行搜索
		t = q.front();
		q.pop();
		// 是否走到终点
		if(t.x == ex && t.y == ey){
			return t.step;
		}
		// 遍历四个方向
		for(int i=0;i<4;i++){
			int xx = t.x + dx[i];
			int yy = t.y + dy[i];
			// 验证下一个点能不能走
			// 不能超过边界  不是障碍物  走过的不能走
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&mp[xx][yy]!='X'&&vis[xx][yy]!=1){
				q.push({xx,yy, t.step+1});
				vis[xx][yy] = 1;
			}
		}
	}
	return -1;
}

int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
			if(mp[i][j] == 'S') sx=i,sy=j;  
			if(mp[i][j] == 'T') ex=i,ey=j;
		}
	}
	cout<<bfs(sx, sy);
	return 0;
}
状态
已结束
题目
4
开始时间
2024-6-8 15:30
截止时间
2024-6-17 23:59
可延期
24 小时