hdu 1241 dfs简单题

最新推荐文章于 2025-06-03 21:31:47 发布

Yonggie

最新推荐文章于 2025-06-03 21:31:47 发布

阅读量246

点赞数

分类专栏：数据结构

本文链接：https://blog.csdn.net/Yonggie/article/details/84541495

版权

数据结构专栏收录该内容

59 篇文章

订阅专栏

本文通过一道编程题目，深入解析了深度优先搜索（DFS）算法的实现与应用。作者分享了从初学者到熟练掌握的过程，展示了如何使用DFS解决迷宫问题，并附上了完整的AC代码。文章强调了实践的重要性，指出通过不断练习可以克服难题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

我是真的发现“会者不难，难者不会”这句话是真的正确。

我五分钟敲完代码一遍AC，可是我刚刚放弃的那道题做了一天都没做出来。

好伤啊兄弟。

一年以前我觉得dfs好难，现在看来像1+1==2差不多……

时间啊时间，你让我头发掉了好多啊！

思路：搜索到 ‘@’ 就把它所在的位置置为 ' * '，这也算是记录走过的路径。

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e2+5;
int dir[8][2]={1,0,0,1,-1,0,0,-1,1,-1,-1,1,1,1,-1,-1};
char mp[maxn][maxn];
int n,m;
void dfs(int x,int y){
	mp[x][y]='*';
	for(int i=0;i<8;i++){
		int xx=x+dir[i][0];
		int yy=y+dir[i][1];
		if(xx>=0&&x<n&&yy>=0&&yy<m&&mp[xx][yy]=='@'){
			dfs(xx,yy);
		}
	}
}
int main(){
	while(cin>>n>>m,n&&m){
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cin>>mp[i][j];
			}
		}
		
		int cnt=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(mp[i][j]=='@'){
					dfs(i,j);
					cnt++;
				}
			}
		}
		cout<<cnt<<endl;
	}
}