例题
找迷宫可以到达的点数量
https://www.acwing.com/problem/content/1115/
找迷宫全部路径
https://www.luogu.com.cn/problem/P1238
DFS模板(不带回溯)
#include <iostream>
#include <cstdio>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
int w,h,ans;
PII dir;
char Map[30][30];
bool vis[30][30];
int dx[4] = {-1,1,0,0}; // 上 下 左 右
int dy[4] = {0,0,-1,1};
bool check(int x,int y)
{
if(x >= 0 && x < w && y >= 0 && y < h && !vis[x][y] && Map[x][y] != '#') return true;
return false;
}
int dfs(int x,int y)
{
int cnt = 1;
vis[x][y] = true;
for(int i = 0; i < 4; i++)
{
int xx = x + dx[i];
int yy = y + dy[i];
if(check(xx,yy))
{
cnt += dfs(xx,yy);
}
}
return cnt;
}
int main()
{
while(scanf("%d%d",&h,&w) != EOF)
{
if(w == 0 && h == 0) break;
for(int i = 0; i < w; i++) scanf("%s",Map[i]);
for(int i = 0; i < w; i++)
for(int j = 0; j < h; j++)
if(Map[i][j] == '@') dir = {i,j};
printf("%d\n",dfs(dir.x,dir.y));
memset(vis,0,sizeof(vis));
}
return 0;
}
DFS模板(带回溯)
#include <iostream>
#include <cstdio>
#include <vector>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
vector<PII> ans;
PII Start,End;
int dx[4] = {0,-1,0,1};
int dy[4] = {-1,0,1,0};
int m,n;
int Map[20][20];
bool vis[20][20];
bool flag;
bool check(int x,int y)
{
if(x > 0 && x <= m && y > 0 && y <= n && Map[x][y] == 1 && !vis[x][y]) return true;
return false;
}
void dfs(int x,int y,vector<PII> &tmp)
{
vis[x][y] = true;
ans.push_back({x,y});
for(int i = 0; i < 4; i++)
{
int xx = x + dx[i];
int yy = y + dy[i];
if(check(xx,yy))
{
if(xx == End.x && yy == End.y)
{
flag = true;
for(int i = 0; i < tmp.size(); i++)
{
printf("(%d,%d)->",tmp[i].x,tmp[i].y);
}
printf("(%d,%d)\n",End.x,End.y);
vis[End.x][End.y] = false;
return;
}
dfs(xx,yy,ans);
vis[xx][yy] = false;
ans.pop_back();
}
}
}
int main()
{
scanf("%d%d",&m,&n);
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
scanf("%d",&Map[i][j]);
}
}
scanf("%d%d",&Start.x,&Start.y);
scanf("%d%d",&End.x,&End.y);
dfs(Start.x,Start.y,ans);
if(!flag) printf("-1\n");
return 0;
}