通过几道例题简单阐述一下DFS的相关题型
ZOJ2412-Farm Irrigation
直观的DFS题型，稍加变化，记录好四个方向上的通路就能够做出来
题目和接水管类似，问最少要灌溉几次，即求解最少有多少个连通子图。
//和接水管游戏类似，将相应水管通路标记清晰即可
//Time:0Ms Memory:270K
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAX 55
#define OPPOSITE(x) ((x + 2) % 4) //x的相反位置
#define MAP(x,y) (map[x][y] - 'A') //水管序列
int row, col;
char map[MAX][MAX];
bool v[MAX][MAX];
int mov[][] = { {, }, {, }, {, -}, {-, } }; //东南西北
bool face[][] = { //face[i][j] ： 在i方向上第j个水管是否有通路
{ ,,,,,,,,,, }, //东
{ ,,,,,,,,,, }, //南
{ ,,,,,,,,,, }, //西
{ ,,,,,,,,,, } //北
};
void dfs(int x,int y)
{
v[x][y] = true;
for (int i = ; i < ; i++)
{
int tx = x + mov[i][];
int ty = y + mov[i][];
if (face[i][MAP(x,y)] && tx >= && tx < row && ty >= && ty < col) //该水管相应对接方向有通路
{
if (!v[tx][ty] && face[OPPOSITE(i)][MAP(tx,ty)]) //对接水管相应方向有通路
dfs(tx, ty);
}
}
}
int main()
{
while (scanf("%d%d", &row, &col), row != - && col != -)
{
memset(v, false, sizeof(v));
for (int i = ; i < row; i++)
scanf("%s", map[i]);
int times = ;
for (int i = ; i < row; i++)
for (int j = ; j < col; j++)
{
if (!v[i][j]) {
times++;
dfs(i, j);
}
}
printf("%d\n", times);
}
return ;
}
ZOJ1008-Gnome Tetravex
看起来不像个搜索题，初看可能会以为需要枚举之类的，但是题中方块的各状态需要记录，在匹配失败时需要回退，因此是一道DFS题型。
大致的解题思路就是先枚举0行0列的方块，再依据此方块固定下一个方块，以此类推，出现不能匹配时回退。
虽然规模最大只有5，但是总方块数25个在DFS中也不可小觑，如果用纯DFS来做，时间度最坏可以达到O((n^2)!)，因此剪枝或其他优化是必须的（只要数据不够水），我在超时后看了很多博客的解题报告（想不到了= =），就该题数据而言最好的优化方法是去重，即将相同方块合在一起，以减少DFS的分支数，但是我总觉得这么做挺奇怪的。。。虽然在大数据下，此题去重很有效果（数字在0-9，因此方块重复概率 < 1/2500），但是此题拿小数据故意出多组重复方块，不得不让人怀疑其心不善...
另外的剪枝方法，也有很多比较有效，但对此题没有太大帮助。
例如：记录各方向上各数字的个数，在匹配时动态增删，如果已经固定的方块需要的对应数字的数量缺失，那么就可以直接回退，剪枝效果在少量随机数据情况下比较好。
//去重就不会超时了，但这个优化实在是...让人感到很意外
//Time:2100ms Memory:272K
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; #define MAX 28 int n, m;
int sq[MAX][]; //上右下左
int board[MAX]; //棋盘上对应位置的square
int v[MAX]; //记录同类sq未被使用的数量 bool dfs(int num)
{
if (num == n*n)
return true;
//找出可以充当第num个方块的i方块
for (int i = ; i < m; i++)
{
if (!v[i]) continue; //没有未固定方块
if (num % n && sq[i][] != sq[board[num - ]][]) continue; //非第一列+不匹配
if (num / n && sq[i][] != sq[board[num - n]][]) continue; //非第一行+不匹配 v[i]--;
board[num] = i;
if (dfs(num + )) return true;
else v[i] ++;
}
return false;
} int main()
{
int t = ;
while (scanf("%d", &n), n)
{
if (t) printf("\n"); memset(v, , sizeof(v));
memset(board, , sizeof(board));
m = ;
for (int i = ; i < n*n; i++)
{
int u, r, d, l;
scanf("%d%d%d%d", &u, &r, &d, &l);
//查重
bool flag = false;
for (int j = ; j < m; j++)
{
if (u == sq[j][] && r == sq[j][] && d == sq[j][] && l == sq[j][])
{
v[j]++;
flag = true;
break;
}
}
if (!flag) {
sq[m][] = u; sq[m][] = r; sq[m][] = d; sq[m][] = l;
v[m++] ++;
}
} if (dfs()) printf("Game %d: Possible\n", ++t);
else printf("Game %d: Impossible\n", ++t);
} return ;
}