2096: 快乐的马里奥
#include <bits/stdc++.h>
using namespace std;
struct node{
int x,y;
};
int n,m,s=1;
int fx[4]={0,-1,0,1},fy[4]={1,0,-1,0};
int a[110][110];
void bfs(int x,int y){
queue<node>q;//创建node队列 q
q.push((node){x,y});//将起始点入队
a[0][0]=s++;//从0,0位置出发
while(!q.empty())
{
node nd =q.front();//获取队首
q.pop();
for(int i=0;i<4;i++){
int w=nd.x+fx[i];
int e=nd.y+fy[i];
if(w>-1&&w<n&&e>-1&&e<m&&a[w][e]==0){
a[w][e]=s++;
q.push(node{w,e});
}
}
}
}
int main(){
cin>>n>>m;
memset(a,0,sizeof(a));
bfs(0,0);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
2097: 走出迷宫
#include <bits/stdc++.h>
using namespace std;
char a[110][110];
struct Node {
int x,y,step;
};
int dx[]= {0,0,1,0,-1};
int dy[]= {0,1,0,-1,0};
int n,m;
queue<Node> q;
int sx,sy,ex,ey;
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>a[i][j];
if(a[i][j]=='S') {
sx=i,sy=j;
a[i][j]='#';
q.push((Node) {sx,sy,0});
} else if(a[i][j]=='T') {
ex=i,ey=j;
a[i][j]='.';
}
}
}
while(!q.empty()) {
Node s= q.front();
q.pop();
if(s.x==ex && s.y==ey) { //达到条件时输出，并直接退出即可
cout<<s.step<<endl;
break;
}
for(int i=1; i<=4; i++) {
int tx=s.x+dx[i],ty=s.y+dy[i],step=s.step+1;
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]=='.') {
a[tx][ty]='#';
q.push((Node) {
tx,ty,step
});
}
}
}
return 0;
}
2099: 迷踪步(BFS)
#include<bits/stdc++.h>
using namespace std;
int a[101][101],vis[101][101];
int n,m;//n和m为矩阵行列
//四个方向搜索
int f4[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
struct node //每个单元格作为一个节点
{ int x,y,dis;};
int BFS(int,int,int);//坐标及最短路径
int main(){
//输入矩阵
cin >> n >> m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin >> a[i][j]; //计算最短路径
cout << BFS(1,1,0);
return 0;
}
int BFS(int x,int y,int z)
{
//起始点标记访问
vis[x][y] = 1;
//声明一个队列
queue <node> q;
//声明队列的起点和下一个点
node start,next;
//设置起始节点属性
start.x = x; start.y = y;
start.dis = z;
q.push(start);//入队
while(!q.empty())//队不为空
{
start = q.front();//获取队首元素
q.pop();//出队
if(start.x == n && start.y == m)//如果当前节点到到最后一个点，返回长度
return start.dis;
for(int i=0;i<=3;i++)//四个方向搜索
{
//获取下一个节点的属性
next.x = start.x + f4[i][0];
next.y = start.y + f4[i][1];
next.dis = start.dis + 1;//下一个节点有路径到达且未访问过
if(a[next.x][next.y] == 0 && !vis[next.x][next.y])
{
vis[next.x][next.y] = 1;//访问
q.push(next);//入队
}
}
}
return -1;
}