深度优先搜索

从起点出发，走过的点要做标记，发现有没走过的点，就随意挑一个往前走，走不了就回退，此种路径搜索策略就称为“深度优先搜索”，简称“深搜”。
其实称为“远度优先搜索”更容易理解些。因为这种策略能往前走一步就往前一
步，总是试图走得更远。
所谓远近(或深度），就是以距离起点的步数来衡量的。
这个过程和递归的性质很像，所以一般用递归来实现这个过程
深度优先搜索其实就是一个不断回溯的过程

图遍历所有的点

例 HDU 1312.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>using namespace std;
int w, h, num;
#define check(x,y)(x<h&&x>=0&&y<w&&y>=0)//判断是否越界
char room[23][23] = { '0' };int dir[4][2] = {//控制方向{0,1},{0,-1},{-1,0},{1,0},
};int color[23][23] = { 0 };//标记数组void dfs(int i, int j) {if (color[i][j]) {//如果是走过的就弹出return;}num++;color[i][j] = 1;for (int t = 0; t < 4; t++) {//对每一个方向遍历int nexti = i + dir[t][0];int nextj = j + dir[t][1];if (room[nexti][nextj] == '.' && check(nexti, nextj)) {//进行搜索dfs(nexti, nextj);}}
}int main()
{int dx, dy;while (cin >> w >> h) {if (w == 0 && h == 0)return 0;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {cin >> room[i][j];if (room[i][j] == '@') {dx = i; dy = j;}}}num = 0;memset(color, 0, sizeof(color));//每次一次搜索前都要把标记数组清零dfs(dx, dy);cout << num << endl;}return 0;
}

找到去某一点的路径

例 HDU 1010.

#include<cstdio>
#include<string.h>
#include<cstdlib>
using namespace std;
char ls[10][10];
int can[10][10];
int N, M, T, i, j, xend, yend, flag, xstart, ystart;
char s[10];
int dxy[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
void dfs(int x, int y, int step)
{if (x == xend && y == yend) {if (step == T) {//如果到门口标记为1，直接结束flag = 1;return;}return;}if (flag == 1) return;for (int i = 0; i < 4; ++i) {//对每一个方向进行搜索int xx = x + dxy[i][0];int yy = y + dxy[i][1];if (xx < 0 || xx >= N || yy < 0 || yy >= M) continue;else if (can[xx][yy] == 1 || ls[xx][yy] == 'X') continue;can[xx][yy] = 1;dfs(xx, yy, ++step);can[xx][yy] = 0;step--;}
}
int main()
{while (1) {char s[8];flag = 0;scanf("%d %d %d", &N, &M, &T);memset(can, 0, sizeof(can));if (N == 0 && M == 0 && T == 0) break;for (i = 0; i < N; i++) {scanf("%s", &s);for (j = 0; j < M; j++) {ls[i][j] = s[j];if (s[j] == 'S') {xstart = i; ystart = j;can[i][j] = 1;}if (s[j] == 'D') {xend = i; yend = j;}}}if ((T - abs(xend - xstart) - abs(yend - ystart)) % 2 != 0 ||//奇偶剪枝T < abs(xend - xstart) + abs(yend - ystart)) {printf("NO\n");continue;}dfs(xstart, ystart, 0);if (flag == 0) printf("NO\n");else printf("YES\n");}return 0;
}