1.前言
大家好啊，今天继续为大家分享俩道洛谷dfs的题目，希望能对大家有所帮助。
2.俩道题目
1.入门（P1683）
1.题目描述
不是任何人都可以进入桃花岛的，黄药师最讨厌像郭靖一样呆头呆脑的人。所以，他在桃花岛的唯一入口处修了一条小路，这条小路全部用正方形瓷砖铺设而成。有的瓷砖可以踩，我们认为是安全的，而有的瓷砖一踩上去就会有喷出要命的毒气，那你就死翘翘了，我们认为是不安全的。你只能从一块安全的瓷砖上走到与他相邻的四块瓷砖中的任何一个上，但它也必须是安全的才行。
由于你是黄蓉的朋友，她事先告诉你哪些砖是安全的、哪些砖是不安全的，并且她会指引你飞到第一块砖上（第一块砖可能在任意安全位置），现在她告诉你进入桃花岛的秘密就是：如果你能走过最多的瓷砖并且没有死，那么桃花岛的大门就会自动打开了，你就可以从当前位置直接飞进大门了。
注意：瓷砖可以重复走过，但不能重复计数。
2.输入格式
第一行两个正整数 W 和 H，分别表示小路的宽度和长度。
以下 H 行为一个 H×W 的字符矩阵。每一个字符代表一块瓷砖。其中 . 代表安全的砖，# 代表不安全的砖，@ 代表第一块砖。
3.输出格式
输出一行，只包括一个数，即你从第一块砖开始所能安全走过的最多的砖块个数（包括第一块砖）。
4.输入输出样例
5.说明/提示
数据规模与约定
对于全部的测试点，保证 1≤W,H≤20。
6.题解
#include<iostream>
#include<algorithm>
using namespace std;
const int N=30;
int w=0,h=0;
int res=0;
bool st[N][N];
char m[N][N];//创建地图
int dx[4]={-1,0,1,0};//向量数组x
int dy[4]={0,1,0,-1};//向量数组y
void dfs(int x,int y){
for(int i=0;i<4;i++){
int a=x+dx[i];int b=y+dy[i];
if(a>=h||b>=w||a<0||b<0)continue;//判断是否越界
if(m[a][b]!='.')continue;//判断是否为.
if(st[a][b])continue;//判断是否走过
st[a][b]=true;//用于记录这个路是否走过
res++;//记录方案
dfs(a,b);//不需要回溯
}
}
int main(){
scanf("%d%d",&w,&h);
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
scanf(" %c",&m[i][j]);
}//双重循环输入地图
}
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(m[i][j]=='@'){ //寻找入口
st[i][j]=true;
dfs(i,j);
}
}
}
res++;
printf("%d",res);
return 0;
}
- 这道题的整体思路就是先利用循环输入地图
- 再利用一个双重循环寻找入口
- 找到入口后开始搜索这道题比较高明的地方就是创建一个向量数组（不用这个就要指数搜索啦，时间会比较长）
- 接着三个判断条件：1.是否越界。2.是否为可走的道路3.是否为已走过的道路。
- 都满足后记录res并继续搜索，最后打印即可
2.Lake Counting S（P1596）
1.题目描述
Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. Given a diagram of Farmer John's field, determine how many ponds he has.
2.输入格式
Line 1: Two space-separated integers: N and M * Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.
3.输出格式
Line 1: The number of ponds in Farmer John's field.
4.题意翻译
由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个 N×M(1≤N≤100,1≤M≤100) 的网格图表示。每个网格中有水（W） 或是旱地（.）。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。
输入第 1 行：两个空格隔开的整数：N 和 M。
第 2 行到第 N+1 行：每行 M 个字符，每个字符是 W 或 .，它们表示网格图中的一排。字符之间没有空格。
输出一行，表示水坑的数量。
5.输入输出样例
6.题解
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=110;
int n=0,m=0;
int res=0;
char ma[N][N];
bool st[N][N];
int dx[8]={1,1,1,0,0,-1,-1,-1};//创建向量数组
int dy[8]={-1,0,1,1,-1,1,0,-1};
void dfs(int x,int y){
for(int i=0;i<8;i++){
int a=x+dx[i];int b=y+dy[i];
if(a<0||b<0||a>=n||b>=m)continue;
if(ma[a][b]!='W')continue;
if(st[a][b])continue;
st[a][b]=true;
dfs(a,b);//不用回溯
}
return ;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%s",ma[i]);//输入地图
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(ma[i][j]=='W'&&!st[i][j]){
dfs(i,j);
res++;
}
}
}
printf("%d\n",res);
return 0;
}
- 这道题思路跟上一题有些类似，但更加复杂了一点。
- 还是先利用循环输入地图（这里直接利用单一循环输入字符数组，时间会更快）。
- 接着利用双重循环寻找第一个水坑位置，开始搜索。
- 从第一个水坑位置开始，开始寻找最多能蔓延到的其他位置（继续利用向量数组），做好标记，保证该水坑最大时搜索结束，水坑数加1。
- 继续在双重循环里面遍历寻找下一个能够注水的地方，依此类推最后输出res即可。
3.小结
今天的分享到这里就结束咯，大家喜欢的话就多多支持吧~
