DFS深度搜索；之前一直和bfs的用法搞不太清楚；写了题才能慢慢参透吧，看了别的博客的代码，感觉能更好理解dfs在图中的应用；
这个题目的意思是一个人去救另一个人，找出最短的寻找路径；
#include<stdio.h>
int n,m,p,q,min=;
int a[][],book[][];
void dfs(int x,int y,int step)
{
int next[][]={
{,},//向右走
{,},//向下走
{,-},//向左走
{-,},//向上走
};
int tx,ty,k;
if(x==p && y==q) //判断是否到达小哈的位置
{
if(step<min)
min=step; //更新最小值
return;
}
/*枚举四种走法*/
for(k=;k<=;k++)
{
/*计算下一个点的坐标*/
tx=x+next[k][];
ty=y+next[k][];
if(tx< || tx>n || ty< || ty>m) //判断是否越界
continue;
/*判断该点是否为障碍物或者已经在路径中*/
if(a[tx][ty]== && book[tx][ty]==)
{
book[tx][ty]=; //标记这个点已经走过
dfs(tx,ty,step+); //开始尝试下一个点
book[tx][ty]=; //尝试结束，取消这个点的标记
}
}
return;
} int main()
{
int i,j,startx,starty;
scanf("%d %d",&n,&m); //读入n和m，n为行，m为列
/*读入迷宫*/
for(i=;i<=n;i++)
for(j=;j<=m;j++)
scanf("%d",&a[i][j]);
scanf("%d %d %d %d",&startx,&starty,&p,&q); //读入起点和终点坐标
/*从起点开始搜索*/
book[startx][starty]=; //标记起点已经在路径中，防止后面重复走
dfs(startx,starty,); //第一个参数是起点的x坐标，以此类推是起点的y坐标，初始步数为0
printf("%d",min); //输出最短步数
return ;
}
然后又写了POJ上叫flip game的游戏，又刷新了我的认知.....
在看了一些代码后，才知道dfs需要考虑做和不做的问题，做了之后dfs，做完恢复，不做就继续走；
#include <stdio.h>
#include <string>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int inf=0x3f3f3f3f;
char map[][];
int dir[][]={{,},{,},{,-},{-,},{,}},minn;
int judge(){
char a=map[][];
for(int i=;i<;++i){
for(int j=;j<;++j){
if(map[i][j]!=map[][])
return ;
}
}
return ;
}
void swap(int x,int y){
for(int i=;i<;++i){
int xx=dir[i][]+x;
int yy=dir[i][]+y;
if(xx>=||yy>=||xx<||yy<)
continue;
if(map[xx][yy]=='b') //变换
map[xx][yy]='w';
else if(map[xx][yy]=='w')
map[xx][yy]='b';
}
}
void dfs(int x,int y,int step){
if(step>)
return; //超过步数 ，break
if(judge()){
minn=minn>step?step:minn; //维护最小值
}
if(y>=){
x++;
y=;
}
if(x>=){
return; //break;
}
for(int j=;j<;++j){
if(j==){
swap(x,y);//换的情况
dfs(x,y+,step+);//按这个路子继续深搜
swap(x,y);//恢复原状
}
else{
dfs(x,y+,step); //不翻；
}
}
}
int main(void){
minn=inf;
for(int i=;i<;++i){
scanf("%s",map[i]);
}
dfs(,,); //从起点开始搜；
if(minn>)//步数比总棋子还多，说明不可能实现全部转换
printf("Impossible\n");
else{
printf("%d\n",minn);
}
return ;
}
这个代码好丑..但是复制上去就懒的删了..
和上一题差不多意思，因为一个点只会被翻一次，翻两次没有意义；
dfs(深度优先搜索)是两个搜索中先理解并使用的，其实就是暴力把所有的路径都搜索出来，它运用了回溯，保存这次的位置，深入搜索，都搜索完了便回溯回来，搜下一个位置，直到把所有最深位置都搜一遍，要注意的一点是，搜索的时候有记录走过的位置，标记完后可能要改回来；
2.bfs(宽度/广度优先搜索)，这个一直理解了思想，不会用，后面才会的，思想，从某点开始，走四面可以走的路，然后在从这些路，在找可以走的路，直到最先找到符合条件的，这个运用需要用到队列(queue)，需要稍微掌握这个才能用bfs；
这是网上找到的dfs与bfs的区别；
贴上一个bfs的板子
int visit[N][N]//用来记录走过的位置
int dir[][]={,-,,,-,,,};
struct node
{
int x,y,bits;//一般是点，还有步数，也可以存其他的
};
queue<node>v;
void bfs1(node p)
{
node t,tt;
v.push(p);
while(!v.empty())
{
t=v.front();//取出最前面的
v.pop();//删除
if(找到符合条件的)
{
做记录；
while(!v.empty()) v.pop();//如果后面还需要用，随手清空队列
return;
}
visit[t.x][t.y]=;//走过的进行标记，以免重复
rep(i,,)//做多次查找
{
tt=t;
tt.x+=dir[i][];tt.y+=dir[i][];//这里的例子是向上下左右查找的
if(如果这个位置符合条件)
{
tt.bits++;//步数加一
v.push(tt); //把它推入队列，在后面的时候就可以用了
}
}
}
}