看到这题没有题解 心中百感焦急(可以直接复制版)

蒙自市蒙自一中马晨烨  •  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* 算法),是非常有意思的一种算法


蒙自市蒙自一中马晨烨  •  1年前

有没有见过沙包那么大的拳头?


蒙自一中邓老师  •  1年前

请先登录,才能进行评论