上海计算机学会2023年12月月赛C++丙组T4迷宫
发布时间
阅读量：
阅读量
迷宫
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定 n×m 个方格构成的图，每个格子都有一种地形：
- 有一些格子是墙，以符号
#表示，墙不可通行。 - 有一些格子是空地，以符号
.表示，空地可以通行。
请计算，从左上角的方格出发，最少需要移动多少步才能到达右下角的方格。在移动过程中，不能进入地形为墙的方格，保证起点与终点方格地形不是墙。且移动时，只能移动到水平或垂直方向相邻的方格。
输入格式
- 第一行：单个整数 n 与 m
- 第二行到第 n+1 行：第 i+1 行每行有 m 个整数表示第 i 行的地形
输出格式
- 单个整数，表示起点到终点最短路径长度
- 若无解，输出
No solution
数据范围
- 30% 的数据，1≤n,m≤4
- 60% 的数据，1≤n,m≤10
- 100% 的数据，1≤n,m≤1000
样例数据
输入:
4 5
.#...
.#.#.
.#.#.
...#.输出:
13输入:
3 3
..#
.#.
#..
输出:
No solution
解析：宽度优先搜索，详见代码：
#include <bits/stdc++.h>
using namespace std;
int n,m;
char a[1005][1005];//地图
int b[1005][1005];//走到这个位置最少用几步
int dx[4]={0,0,-1,1};//四个方向
int dy[4]={-1,1,0,0};
struct node{
int x,y;
};
queue <node> q;//队列
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
node t;
t.x=1;t.y=1;
q.push(t);//起点入队
while (!q.empty()){
int x=q.front().x;//队首出队
int y=q.front().y;
q.pop();
for(int i=0;i<4;i++){//枚举四个方向
int xx=x+dx[i];
int yy=y+dy[i];
//不出界且不是墙，也没走过
if (xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]=='.'&&b[xx][yy]==0){
b[xx][yy]=b[x][y]+1;//计算步数
t.x=xx;
t.y=yy;
q.push(t);//入队
}
}
}
if(b[n][m]==0){
cout<<"No solution";
}else{
cout<<b[n][m];
}
return 0;
}
全部评论 (0)
还没有任何评论哟~