搜索
一、深度优先搜索
图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。
它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
显然，深度优先搜索是一个递归的过程。
深度优先遍历特点是，选定一个出发点后进行遍历，能前进则前进，若不能前进，回退一步再前进，或再回退一步后继续前进。依此重复，直到所有与选定点相通的所有顶点都被遍历。
例1：走迷宫，S为起点，T为终点，.为路，X为墙，输出能否走通
#include <iostream>
#include <stack>
#include <cstring>
#define MAX 1005
using namespace std;
char c;
int mg[MAX][MAX],n,m,sx,sy,tx,ty;
int direction[4][2]={ {0,1},{1,0},{0,-1},{-1,0} };
stack<int> s;
bool visit[MAX][MAX],flg;
void dfs(int x,int y)
{
if(x==tx&&y==ty)
{
flg=true;
return;
}
if(mg[x][y]==0)
return;
visit[x][y]=true;
for(int i=0;i<=3;i++)
if(!visit[x+direction[i][0]][y+direction[i][1]])
dfs(x+direction[i][0],y+direction[i][1]);
visit[x][y]=false;
return;
}
int main()
{
while(cin>>n>>m)
{
flg=false;
memset(mg,0,sizeof(mg));
memset(visit,false,sizeof(visit));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>c;
if(c=='.'||c=='S'||c=='T')
mg[i][j]=1;
if(c=='S')
sx=i,sy=j;
if(c=='T')
tx=i,ty=j;
}
dfs(sx,sy);
if(flg)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
例2：Luogu P1596
