【DFS解决连通性模型问题】在判断一个图中两点是否联通的时候（或连通块中点的数量），可以采取DFS或者BFS 。DFS与BFS相比，DFS的代码更简短 。
递归与回溯：
DFS参数传入当前的坐标；
往一个方向偏移后递归到下一层；
回溯后向另一个方向偏移 。
例题1：迷宫
给定一个矩阵迷宫，问是否可以从给定的起点走到终点 。矩阵中‘#’代表无法通过，'.'代表可以通过，第一行输入数据组数，后序输入数据 。
样例说明：
2组数据，第一组数据矩阵大小3*3，判断(0,0)到(2,2)是否联通，第二组数据矩阵大小5*5，判断(0,0)到(4,0)是否联通 。
代码如下：
#include#includeusing namespace std;const int N = 110;char g[N][N];//迷宫bool st[N][N];//状态数组，记录是否走过了int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };//偏移量int x1, x2, y1, y2;int n, m;bool dfs(int x, int y) {if (g[x][y] == '#')return false;//起点可能为'#'if (x == x2 && y == y2)return true;//如果到达目标点st[x][y] = true;//该点已经走过了for (int i = 0; i < 4; i++) {//遍历该点的上下左右int a = x + dx[i], b = y + dy[i];if (a < 0 || a >= m || b < 0 || b >= m)continue;//越界了if (st[a][b])continue;//走过了if (g[a][b] == '#')continue;//走不通if (dfs(a, b))return true;//往后走，如果后面走到了就返回true}return false;//如果全部搜完还没有}int main() {cin >> n;//n组数据while (n--) {//读入每组数据memset(st, 0, sizeof st);//每组数据都要初始化stcin >> m;for (int i = 0; i < m; i++)for (int j = 0; j < m; j++)cin >> g[i][j];cin >> x1 >> y1 >> x2 >> y2;if (dfs(x1, y1))cout << "YES" << endl;else cout << "NO" << endl;}return 0;}
例题2：红与黑
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖 。你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动 。请写一个程序，计算你总共能够到达多少块黑色的瓷砖 。输入0 0表示结束，有多组数据 。
代码如下：
#include#includeusing namespace std;const int N = 25;char g[N][N];bool st[N][N];int n, m, x, y;int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };int res;void dfs(int xa, int ya) {if (!st[xa][ya]) { res++; st[xa][ya] = true; }//如果没走过，也可也省去这个判断for (int i = 0; i < 4; i++) {//四个偏移量int a = xa + dx[i], b = ya + dy[i];if (a < 0 || a >= n || b < 0 || b >= m) continue;if (g[a][b] != '.') continue;if (st[a][b]) continue;dfs(a, b);}return;}int main() {while (1) {//读入数据cin >> m >> n;//m列n行if (m == 0 || n == 0)return 0;//输入0就结束for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) {cin >> g[i][j];if (g[i][j] == '@') { x = i; y = j; }//记录站的位置}memset(st, 0, sizeof st);res = 0;dfs(x, y);//搜cout << res << endl;}return 0;}
