前言：
这篇文章里的题和BFS那篇2025级大一ACM训练：搜索入门（一）：BFS-CSDN博客几乎是一样的，这里用DFS的思想来做。这里面我收获最大的题是面积（area）-搜索
林大OJ 558：迷宫寻路-搜索
特点：因为只有两个口，我们只要找到入口出口，通过dfs判断出口判断是否为#就可以了
ps：new_x, new_y定义成局部变量！！这道题定义成全局变量是没有影响。
#include <bits/stdc++.h>
using namespace std;
int m,n;
char a[1005][1005];
int start_x, start_y, end_x, end_y, new_x, new_y;
int dirc[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0,-1}};
void seek_begin()
{
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
if(a[i][j] == '*' &&( i == 0 || i == n-1 || j == 0 || j ==m-1)) {start_x = i; start_y = j; return;}//注意这里的()
}
}
void seek_end()
{
for(int i = n-1; i>=0; i–)//i和j从n-1和m-1开始
for(int j = m-1; j >= 0; j–)
{
if(a[i][j] == '*' && (i == n-1 || i == 0 || j == 0 || j == m-1)){end_x = i; end_y = j; return;}
}
}
void dfs(int x, int y)
{
a[x][y] = '#';
for(int i = 0; i < 4; i++)
{
new_x = x + dirc[i][0];
new_y = y + dirc[i][1];
if(new_x >= 0 && new_x < n && new_y >= 0 && new_y < m && a[new_x][new_y] == '*')
dfs(new_x, new_y);
}
}
int main()
{
ios::sync_with_stdio(false);
while(cin>>n>>m)
{
for(int i = 0; i < n; i++)
cin>>a[i];
seek_begin();
seek_end();
dfs(start_x, start_y);
if(a[end_x][end_y] == '#')
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
林大OJ 784：白与黑-搜索
特点：需要全遍历完，cnt可以初始化为0，在dfs函数开头cnt++。
#include <bits/stdc++.h>
using namespace std;
int W,H,cnt;
int start_x, start_y, new_x, new_y;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char a[25][25];
void seek_begin()
{
for(int i = 0; i < H; i++)
for(int j = 0; j < W; j++)
{
if(a[i][j] == '@'){start_x = i; start_y = j; a[i][j] = '#'; return;}
}
}
void dfs(int x, int y)
{
for(int i = 0; i < 4; i++)
{
new_x = x + dir[i][0];
new_y = y + dir[i][1];
if(new_x >= 0 && new_x < H && new_y >= 0 && new_y < W && a[new_x][new_y] == '.')
{
a[new_x][new_y] = '#';
cnt++;
dfs(new_x, new_y);
}
}
}
int main()
{
ios::sync_with_stdio(false);
while(cin>>W>>H)
{
for(int i = 0; i < H; i++)
cin>>a[i];
cnt = 1;
seek_begin();
if(W == 0 && H == 0)
break;
dfs(start_x,start_y);
cout<<cnt<<endl;
}
return 0;
}
林大OJ 912：搜索入门-搜索
特点：dfs中有特定的结束条件
注意：nx 和 ny 定义为局部变量：每次递归都会创建独立的nx/ny，上层的nx/ny不会被下层覆盖
两个return true?
第一个 return true：我已经到终点了！
第二个 return true：我探索的方向能到终点，所以我这一层也能到终点！
#include <iostream>
using namespace std;
const int SIZE = 4;
char maze[SIZE][SIZE];
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool dfs(int x, int y) {
if (x == SIZE – 1 && y == SIZE – 1) {
return true;
}
maze[x][y] = '*';
for (int i = 0; i < 4; ++i) {
int nx = x + dirs[i][0];
int ny = y + dirs[i][1];
if (nx >= 0 && nx < SIZE && ny >= 0 && ny < SIZE && maze[nx][ny] == '#') {
if (dfs(nx, ny)) {
return true;
}
}
}
return false;
}
int main() {
int n;
cin >> n;
while (n–) {
for (int i = 0; i < SIZE; ++i) {
cin >> maze[i];
}
cout<<(dfs(0, 0) ? "YES" : "NO")<<endl;
}
return 0;
}
林大OJ 1696：猴群-搜索
特点：通过dfs来确定连通区域数量
注意：在主函数里 if 判断时不能写 if (a[i][j]) 而是 if (a[i][j] != ‘0’)
#include <iostream>
using namespace std;
int n, m,cnt;
int dirc[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0,-1}};
char a[105][105];
void dfs(int x, int y)
{
a[x][y] = '0';
for(int i = 0; i < 4; i++)
{
int new_x = x + dirc[i][0];
int new_y = y + dirc[i][1];
if(new_x >= 0 && new_x < n && new_y >= 0 && new_y < m &&a[new_x][new_y] != '0')
{
dfs(new_x, new_y);
}
}
}
int main ()
{
ios::sync_with_stdio(false);
while(cin>>n>>m)
{
cnt = 0;
for(int i = 0; i < n; i++)
cin>>a[i];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
if(a[i][j] != '0')
{
dfs(i, j);
cnt++;
}
}
cout<<cnt<<endl;
}
return 0;
}
林大OJ 1694：最大黑色区域-搜索
注意：
1.在输入每组数据后立马初始化max_cnt为0，在每次dfs后进行cnt 与 max_cnt的比较,在dfs内部我们cnt++
2.输入为什么不能用 cin>>a[i]?
用这个会输出Output Limit Exceeded。题目要求的是每行的元素是用空格分隔的整数，不是 “连续的字符串 / 字符”，而cin读取char[]的规则是：遇到空格 / 换行符就停止读取；以第一行为例，cin>>a[0]只会读取第一个0，剩下的1 1 0 0 1会被后续的cin>>a[1]、cin>>a[2]等错误读取；
#include <iostream>
using namespace std;
int n, m,max_cnt,cnt;
int dirc[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0,-1}};
char a[105][105];
void dfs (int x, int y)
{
a[x][y] = '0';
cnt++;
for(int i = 0; i < 4; i++)
{
int new_x = x + dirc[i][0];
int new_y = y + dirc[i][1];
if(new_x >= 0 && new_x < n && new_y >= 0 && new_y < m && a[new_x][new_y] == '1')
dfs(new_x, new_y);
}
}
int main()
{
ios::sync_with_stdio(false);
while(cin>>n>>m)
{
max_cnt = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin>>a[i][j];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
if(a[i][j] == '1')
{
cnt = 0;
dfs(i, j);
if(cnt > max_cnt) max_cnt = cnt;
}
}
cout<<max_cnt<<endl;
}
return 0;
}
林大OJ 1693：瓷砖-搜索
#include <iostream>
using namespace std;
int w, h,cnt,start_x,start_y;
int dirc[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0,-1}};
char a[1005][1005];
void seek_start()
{
for(int i = 0; i < h; i++)
for(int j =0; j < w; j++)
{
if(a[i][j] == '@'){start_x = i; start_y = j; return;}
}
}
void dfs (int x, int y)
{
a[x][y] = '#';
cnt++;
for(int i = 0; i < 4; i++)
{
int new_x = x + dirc[i][0];
int new_y = y + dirc[i][1];
if(new_x >= 0 && new_x < h && new_y >= 0 && new_y < w && a[new_x][new_y] == '.')
{
dfs(new_x, new_y);
}
}
}
int main()
{
ios::sync_with_stdio(false);
while(cin>>w>>h)
{
for(int i = 0; i < h; i++)
cin>>a[i];
seek_start();
cnt = 0;
dfs(start_x, start_y);
cout<<cnt<<endl;
}
return 0;
}
林大OJ 1699：面积（area）-搜索
这道题我一开始没有思路，看了陈宇老师的题解才恍然大悟，但是与他的做法不同的是，我用的是dfs来做的
需要注意的是：我们在主函数中dfs不能只调用一次，若那样做，只标记了seek_start()找到的第一个 0的连通区域，但网格边界上可能有多个不连通的 0，这些未被标记的外围 0 会被误统计为 “内部 0”，导致结果错误。所以我们选择遍历四条边界来寻找所有的0起点
for (int i = 0; i < 10; i++) {
if (a[0][i] == '0') dfs(0, i);
if (a[9][i] == '0') dfs(9, i);
}
for (int i = 1; i < 9; i++) {
if (a[i][0] == '0') dfs(i, 0);
if (a[i][9] == '0') dfs(i, 9);
}
#include <bits/stdc++.h>
using namespace std;
int cnt;
int dirc[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0,-1}};
char a[11][11];
void dfs(int x, int y)
{
a[x][y] = '1';
for(int i = 0; i < 4; i++)
{
int new_x = x + dirc[i][0];
int new_y = y + dirc[i][1];
if(new_x >= 0 && new_x < 10 && new_y >= 0 && new_y < 10 && a[new_x][new_y] == '0')
dfs(new_x, new_y);
}
}
int main ()
{
ios::sync_with_stdio(false);
cnt = 0;
for(int i = 0; i < 10; i++)
for(int j = 0; j < 10; j++)
cin>>a[i][j];
for (int i = 0; i < 10; i++) {
if (a[0][i] == '0') dfs(0, i);
if (a[9][i] == '0') dfs(9, i);
}
for (int i = 1; i < 9; i++) {
if (a[i][0] == '0') dfs(i, 0);
if (a[i][9] == '0') dfs(i, 9);
}
for(int i = 0; i < 10; i++)
for(int j = 0; j < 10; j++)
{
if(a[i][j] =='0')
cnt++;
}
cout<<cnt<<endl;
return 0;
}
