DFS深度优先搜索算法
2024-10-09 17:47:03
Lake Counting(POJ No.2386)
有一个大小为N*M的园子，雨后积起了水。八连通的积水被认为是在一起的。请求出园子里共有多少个水洼？(八连通是指下图中相对w的*部分)
* * *
*w*
* * *
限制条件 N，M ≤ 100
思路：
先遍历整个园子，从任意的w开始，把周围所有的w都变成 '.' ，然后遍历完成之后 res 加1
dfs中的操作就是先把当前位置改为'.'，然后再把周围上下左右邻近的8个位置全部遍历一遍找w，找到w就从那个w的位置再开始周围8个位置的寻找，一直到周围的w找完为止
int N = 10;
int M = 12;
char field[10][12] = {
{'w','.','.','.','.','.','.','.','.','w','w','.'},
{'.','w','w','w','.','.','.','.','.','w','w','w'},
{'.','.','.','.','w','w','.','.','.','w','w','.'},
{'.','.','.','.','.','.','.','.','.','w','w','.'},
{'.','.','.','.','.','.','.','.','.','w','.','.'},
{'.','.','w','.','.','.','.','.','.','w','.','.'},
{'.','w','.','w','.','.','.','.','.','w','w','.'},
{'w','.','w','.','w','.','.','.','.','.','w','.'},
{'.','w','.','w','.','.','.','.','.','.','w','.'},
{'.','.','w','.','.','.','.','.','.','.','w','.'},
}; void dfs(int x, int y)
{
field[x][y] = '.';
for (int dx = -1; dx <= 1; dx++)
{
for (int dy = -1; dy <= 1; dy++)
{
int nx = x + dx;
int ny = y + dy;
if (field[nx][ny] == 'w')
{
dfs(nx, ny);
}
}
}
} int solve()
{
int res = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (field[i][j] == 'w')
{
dfs(i, j);
res++;
}
}
}
return res;
}
最新文章
- CSS知识总结（五）
- jquery修改带!important的css样式
- java学习第19天（异常）
- webservice 学习笔记
- jenkins2 pipeline 语法快速参考
- 【MFC】无边框窗体 WS_THICKFRAME
- CSS3中样式顺序
- Sqli-labs less 43
- 【技术宅4】如何把M个苹果平均分给N个小朋友
- spring mvc ModelAndView向前台传值
- javascript的方法
- MySQL死锁案例分析与解决方案
- 基于Centos7的autobahn-python+crossbar的环境搭建
- Nginx入门基础（一）
- jqweui Picker使用一个小问题
- luogu1345 奶牛的电信 (最小割)
- [转载]oracle的常用函数 instr() 和substr()函数
- TZOJ 3305 Hero In Maze II(深搜)
- bash多进程
- cocos2d-js V3.0 V3.1使用DragonBones