hnsfdxyc

用户名：00000152

访问量：24623

签　名：

等　　级
排　　名	362
经　　验	5240
参赛次数	0
文章发表	24
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

树了解一下（c++）
浏览：362

图的深度优先遍历
浏览：314

你可能喜欢

Minesweeper -（用队列，bfs）

　　作者: hnsfdxyc　　　　发表时间：2019-06-25 17:28:25 浏览：282　|　评论：0　

原题链接：Minesweeper

#### 解题思路：
宽度优先搜索（bfs）按照开始状态由近及远的顺序进行搜索，因此本题中我们可以采用该方法来求解。

------------

1. 本题中，状态仅仅是目前所在位置的坐标，因此可以构造成pair或者编码成int来表示状态。当状态更加复杂时，则需要封装成一个类来表示状态了。

1. 转移的方式为八方向移动，用dx[8],dy[8]两个数组来表示八个方向向量。这样就可以通过循环来实现八个方向的遍历。状态数与地图的大小（NxM）是相等的，所以复杂度是O(8xNxM)=O(NxM)。

1. bfs中，只要将已经访问过的状态用标记管理起来，就可以很好的做到由远及近的搜索。这个问题中，我用go[n][m]数组把状态保存起来。初始化为0，这样尚未达到的位置就是0，也就同时起到了标记作用。

------------
##### 一起来看代码吧
```cpp
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 101;
typedef pair<int,int> P;
int n, m;
char map[maxn][maxn];
int go[maxn][maxn];
//上、下、左、右 、左上、右上、左下、右下 
int dx[8] = {0,0,-1,1,-1,1,1,-1};
int dy[8] = {1,-1,0,0,1,1,-1,-1};

int bfs()
{
	queue<P> que;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		{
			if(map[i][j] == '*')
				que.push(P(i,j));  //将'*'的位置加入队列 
		}
			
	//不断循环直到队列长度为0 
	while(que.size()) 
	{
		//从队列最前端取出元素
		P p = que.front();
		que.pop();
		for(int i=0;i<8;i++)
		{ 
			//移动后的位置记为(nx,ny) 
			int nx = p.first + dx[i];
			int ny = p.second + dy[i];
			//保证移动的位置不超过地图的大小 
			if(nx >= 0 && nx < n && ny >= 0 && ny < m)
			{
				go[nx][ny]++;
			}
		 } 
	}
}
int main()
{
	int cnt = 1;
	while(cin >> n >> m && n!=0 && m!=0)
	{
		memset(map,0,sizeof(map));  //初始化 
		memset(go,0,sizeof(go));    //初始化 
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
			{
				cin >> map[i][j];
			}
				
		bfs();
		printf("Field #%d:\n",cnt);
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(map[i][j] == '*')
					cout << '*';
				else
					cout << go[i][j];
			}
			cout<<endl;
		}
		cout<<endl;
		cnt++;
	}
	return 0;
}

```
欢迎小伙伴留言，一起学习交流哦！

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

hnsfdxyc

TA的其他文章

你可能喜欢

Scanf函数能否接收空格？

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

注意格式（C语言代码）

IP判断（C语言代码）

Minesweeper -（用队列，bfs）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

矩阵乘方（C语言代码）

【偶数求和】（C语言代码）

演讲大赛评分（C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

计算质因子（C语言代码）

矩阵的对角线之和（C语言代码）

剔除相关数（C语言代码）

hnsfdxyc

TA的其他文章

你可能喜欢

Scanf函数能否接收空格？

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

注意格式（C语言代码）

IP判断 （C语言代码）

Minesweeper -（用队列，bfs）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

矩阵乘方 （C语言代码）

【偶数求和】 （C语言代码）

演讲大赛评分 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

计算质因子 （C语言代码）

矩阵的对角线之和 （C语言代码）

剔除相关数 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

IP判断（C语言代码）

　　评论区

矩阵乘方（C语言代码）

【偶数求和】（C语言代码）

演讲大赛评分（C语言代码）

计算质因子（C语言代码）

矩阵的对角线之和（C语言代码）

剔除相关数（C语言代码）