蒙自市蒙自一中马晨烨 • 1年前
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 55;
int n, m, sx, sy, sum;//n,m是图的边长 sx和sy是初始位置 sum来统计瓷砖数
int mv[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; //定义朝四个方向走
char room[Maxn][Maxn];//这里用 char型二位数组方便取值
#define ENGE(x,y)(x>=0&&x<m&&y>=0&&y<n)//用define函数来判断是否在边界内
struct AC {
int x, y;
};//AC寓意好 拿来存坐标
void init() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> room[i][j];
if (room[i][j] == '@')
sx = i, sy = j; //找到阔巴鸭西(小林)的位置:)
}
}
/*for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cout << room[i][j] << " ";
}
puts("");
}*///这里主要是为了看看我输入的部分是否正确
sum = 1;
}
void bfs(int sx, int sy) {
queue<AC> node;//用队列来做bfs
AC now, start, next;
start.x = sx, start.y = sy;
node.push(start);//把初始位置压进当前的队列
while (!node.empty()) {
now = node.front();
node.pop();
for (int i = 0; i < 4; i++) {
next.x = now.x + mv[i][0];
next.y = now.y + mv[i][1];
if (ENGE(next.x, next.y) && room[next.x][next.y] == '.') {
room[next.x][next.y] = '@';//用'@'来把刚刚走的路给标记一下
sum++;//有'.'说明有目的瓷砖
node.push(next);//预期走的这一步是合法的 所以压进队列
}
}
}
}
int main() {
init();
bfs(sx, sy);//从阔巴鸭西(小林)的位置开始"走迷宫"
//cout << sx << " " << sy << endl;//看看初始位置是否有问题
cout << sum;
return 0;
}//华丽结束:)
评论:
这个板是我见过比较完整而且方便记忆的一个bfs模板,大家可以好好记一下,真的还是非常有用的,而且以后加上当前点到终点的曼哈顿距离为该点的权值(及把它捆绑到结构体中)然后使用优先队列来做bfs就可以获得一个高效的寻路方法(a* 算法),是非常有意思的一种算法
请先登录,才能进行评论