DFS简介

DFS基本概念

深度优先搜索算法（Depth First Search）：一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。属于盲目搜索,最糟糕的情况算法时间复杂度为 $O(n^2)$ 。

经典例题

P1706全排列问题

注：题目来源自洛谷。

题目描述

输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 n。

输出格式

由1∼n 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 5 个场宽。

输入输出样例

输入 #1

输出 #1

1    2    3
1    3    2
2    1    3
2    3    1
3    1    2
3    2    1

说明/提示

$1≤n≤9$

答案解析

#include <iostream>
using namespace std;
bool vis[100];//标记数字是否出现
int a[100];//全排列数组
int n;
void dfs(int x)
{
    if (x == n+1)
    {
        for (int i = 1;i <= n;i++)
                printf ("%5d",a[i]);
        cout<<endl;
        return;
    }
    for (int i = 1;i <= n;i++)
    {
        if (vis[i]==0)
        {
            vis[i] = 1;
            a[x] = i;
            dfs(x+1);//递归
            vis[i] = 0;//回溯
        }
    }
}
int main()
{
    cin>>n; 
    dfs(1);
    return 0;
}

P1238 走迷宫

注：题目来源洛谷。

题目描述

有一个 $m\times n$ 格的迷宫(表示有 $m$ 行、 $n$ 列)，其中有可走的也有不可走的，如果用 $1$ 表示可以走， $0$ 表示不可以走，文件读入这 $m\times n$ 个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用 $-1$ 表示无路）。

优先顺序：左上右下。数据保证随机生成。

输入格式

第一行是两个数 $m,n(1<m,n<15)$ ，接下来是 $m$ 行 $n$ 列由 $1$ 和$ 0$ 组成的数据，最后两行是起始点和结束点。

输出格式

所有可行的路径，描述一个点时用 $(x,y)$ 的形式，除开始点外，其他的都要用 -> 表示方向。

如果没有一条可行的路则输出 $-1$ 。

输入输出样例

输入 #1

5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6

输出 #1

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

说明/提示

数据保证随机生成。事实上，如果 $n=m=14$ 且每个位置都是 $1$ 的话，有 $69450664761521361664274701548907358996488$ 种路径。

答案解析

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1001;
bool map[N][N];
bool visited[N][N];
int output[N * N];//stack
int pointer;
bool solution;
//for example, m=5,n=6
//(2,3)==>(2-1)*n+3=9
//(5,6)==>(5-1)*n+6=30
//therefore, (x,y)==>(x-1)*n+y
void dfs(int x, int y);
int m, n, start_x, start_y, end_x, end_y;
int main()
{
	cin >> m >> n;
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			cin >> map[i][j];
	cin >> start_x >> start_y;
	cin >> end_x >> end_y;
	if (map[start_x][start_y] == 0)
	{
		cout << "-1";
		return 0;
	}	
	else if (map[end_x][end_y] == 0)
	{
		cout << "-1";
		return 0;
	}
	else 
		dfs(start_x,start_y);
	if (!solution)
		cout << "-1";
	return 0;
}
void dfs(int x,int y)
{
	if (x<1 || y<1 || x>m || y> n)
		return;
	if (visited[x][y] || !map[x][y])
		return;
	if (x == end_x && y == end_y)
	{
		solution = 1;
		for (int i = 0; i < pointer; i++)
			if (output[i] % n)
				cout << "(" << output[i] / n + 1 << "," << output[i] % n << ")" << "->";
			else
				cout << "(" << output[i] / n  << "," << n << ")" << "->";
		cout << "(" << end_x << "," << end_y << ")" << endl;
		return;
	}

	//++++++++++
	visited[x][y] = true;
	output[pointer] = (x - 1) * n + y;
	pointer++;	
	//++++++++++

	if (map[x][y - 1] && !visited[x][y-1])
		dfs(x, y - 1);
	if (map[x - 1][y] && !visited[x-1][y])
		dfs(x - 1, y);
	if (map[x][y + 1] && !visited[x][y+1])
		dfs(x, y + 1);
	if (map[x + 1][y] && !visited[x+1][y])
		dfs(x + 1, y);

	//----------
	output[pointer] = 0;
	pointer--;
	visited[x][y] = false;
	//----------


}

连通块问题（floodfill）

注：我忘了在哪找的题了。。。

题目描述

一个 $n \times m$ 的方格图，一些格子被涂成了黑色，在方格图中被标为 $1$ ，白色格子标为 $0$ 。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域，其中的每个黑色格子能通过四连通的走法（上下左右），只走黑色格子，到达该联通块中的其它黑色格子。

输入输出样例

输入 #1

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

输出 #1

答案解析

#include<bits/stdc++.h>
using namespace std;
#define maxn 100+5
char pic[maxn][maxn];//存图
int m,n,idx[maxn][maxn];
void dfs(int r,int c,int id)
{
    if(r<0||r>=m||c<0||c>=n)
        return ;//出界的格子
    if(idx[r][c]>0||pic[r][c]!='@')
        return ;//不是'@'或已经被访问过
    idx[r][c]=id;//将点记录下来
    for(int dr=-1;dr<=1;dr++)
        for(int dc=-1;dc<=1;dc++)
            if(dr!=0||dc!=0)
                dfs(r+dr,c+dc,id);//向四个方向搜索·
}
int main()
{
    while(scanf("%d%d",&m,&n)==2 && m && n)
    {
        for(int i=0;i<m;i++)
            scanf("%s",pic[i]);
        memset(idx,0,sizeof(idx));
        int cnt=0;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)//每一次扫描所有为id的方格
                if(idx[i][j]==0&&pic[i][j]=='@')
                    dfs(i,j,++cnt);
        printf("%d\n",cnt);
    }
    return 0;
}

END