今天打算复习dfs的题目：
1.连通性模型
1112. 迷宫 - AcWing题库
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 n∗n�∗� 的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。
同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。
如果起点或者终点有一个不能通行(为#)，则看成无法办到。
注意：A、B不一定是两个不同的点。
输入格式
第1行是测试数据的组数 k�，后面跟着 k� 组输入。
每组测试数据的第1行是一个正整数 n�，表示迷宫的规模是 n∗n�∗� 的。
接下来是一个 n∗n�∗� 的矩阵，矩阵中的元素为.或者#。
再接下来一行是 4 个整数 ha,la,hb,lbℎ�,��,ℎ�,��，描述 A� 处在第 haℎ� 行, 第 la�� 列，B� 处在第 hbℎ� 行, 第 lb�� 列。
注意到 ha,la,hb,lbℎ�,��,ℎ�,�� 全部是从 0 开始计数的。
输出格式
k行，每行输出对应一个输入。
能办到则输出“YES”，否则输出“NO”。
数据范围
1≤n≤1001≤�≤100
输入样例：
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0
输出样例:
YES
NO先自己思考：
-------------------------------------------------------------------------
答案：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
const int N = 110;
char g[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n;
int dfs(int x,int y,int c,int d)
{
if(g[x][y]=='#') return 0;
if(x==c && y==d) return 1;
st[x][y]=1;
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<0 || a>=n || b<0 || b>=n ) continue;
if(st[a][b]) continue;
if(dfs(a,b,c,d)) return 1;
}
return 0;
}
int main()
{
int T;
cin>>T;
while(T--)
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%s",g[i]);
memset(st, 0, sizeof st);
int a,b,c,d;
scanf("%d %d %d %d",&a,&b,&c,&d);
if(dfs(a,b,c,d)) puts("YES");
else puts("NO");
}
return 0;
}
2.dfs之搜索顺序：
1116. 马走日 - AcWing题库
马在中国象棋以日字形规则移动。
请编写一段程序，给定 n∗m�∗� 大小的棋盘，以及马的初始位置 (x，y)(�，�)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。
输入格式
第一行为整数 T�，表示测试数据组数。
每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标 n,m,x,y�,�,�,�。
输出格式
每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，若无法遍历棋盘上的所有点则输出 0。
数据范围
1≤T≤91≤�≤9,
1≤m,n≤91≤�,�≤9,
1≤n×m≤281≤�×�≤28,
0≤x≤n−10≤�≤�−1,
0≤y≤m−10≤�≤�−1
输入样例：
1
5 4 0 0
输出样例：
32答案：
-------------------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N = 35;
int res;
bool st[N][N];
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
void dfs(int x,int y,int cnt)
{
if(cnt==n*m)
{
res++;
}
st[x][y]=1;
for(int i=0;i<8;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<0 || a>=n || b<0 || b>=m) continue;
if(st[a][b]) continue;
dfs(a,b,cnt+1);
}
st[x][y]=0;
}
int main()
{
int T;
cin>>T;
while(T--)
{
int x,y;
scanf("%d%d%d%d", &n, &m, &x, &y);
memset(st, 0, sizeof st);
res=0;
dfs(x,y,1);
printf("%d\n",res);
}
return 0;
}
-------------------------------------------------------------------
3.dfs搜索顺序练习
1117. 单词接龙 - AcWing题库
单词接龙是一个与我们经常玩的成语接龙相类似的游戏。
现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”，每个单词最多被使用两次。
在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish ，如果接成一条龙则变为 beastonish。
我们可以任意选择重合部分的长度，但其长度必须大于等于1，且严格小于两个串的长度，例如 at 和 atide 间不能相连。
输入格式
输入的第一行为一个单独的整数 n� 表示单词数，以下 n� 行每行有一个单词（只含有大写或小写字母，长度不超过20），输入的最后一行为一个单个字符，表示“龙”开头的字母。
你可以假定以此字母开头的“龙”一定存在。
输出格式
只需输出以此字母开头的最长的“龙”的长度。
数据范围
n≤20�≤20，
单词随机生成。
输入样例：
5
at
touch
cheat
choose
tact
a
输出样例：
23
提示
连成的“龙”为 atoucheatactactouchoose。
答案：
----------------------------------------------
#include<bits/stdc++.h>
using namespace std;
const int N = 21;
int n;
string word[N];//存储单词
int g[N][N];//存储单词与另一个单词重合部分的长度
int used[N];//这个单词杯=被用过几次，第二次无法使用
int ans;//龙的长度
void dfs(string dragon,int last)
{
ans=max((int)dragon.size(),ans);
used[last]++;
for(int i=0;i<n;i++)
if(g[last][i] && used[i]<2)
dfs(dragon+word[i].substr(g[last][i]), i);
used[last]--;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>word[i];
char start;
cin>>start;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
string a=word[i],b=word[j];
for(int k=1;k<min(a.size(),b.size());k++)
{
if(a.substr(a.size()-k,k)==b.substr(0,k))
{
g[i][j]=k;
break;
}
}
}
}
for(int i=0;i<n;i++)
{
if(word[i][0]==start)
{
dfs(word[i],i);
}
}
cout<<ans<<endl;
return 0;
}
-----------------------------------------------
