DFS深度搜索；之前一直和bfs的用法搞不太清楚；写了题才能慢慢参透吧，看了别的博客的代码，感觉能更好理解dfs在图中的应用；

这个题目的意思是一个人去救另一个人，找出最短的寻找路径；

#include<stdio.h>
int n,m,p,q,min=99999999;
int a[51][51],book[51][51];
void dfs(int x,int y,int step)
{
    int next[4][2]={
    {0,1},//向右走
    {1,0},//向下走
    {0,-1},//向左走
    {-1,0},//向上走 
    };
    int tx,ty,k;
    if(x==p && y==q)  //判断是否到达小哈的位置 
    {
        if(step<min)
            min=step;  //更新最小值
        return; 
    }
    /*枚举四种走法*/ 
    for(k=0;k<=3;k++)
    {
        /*计算下一个点的坐标*/
        tx=x+next[k][0];
        ty=y+next[k][1];
        if(tx<1 || tx>n || ty<1 || ty>m)  //判断是否越界
            continue;
        /*判断该点是否为障碍物或者已经在路径中*/
        if(a[tx][ty]==0 && book[tx][ty]==0)
        {
            book[tx][ty]=1;  //标记这个点已经走过
            dfs(tx,ty,step+1);  //开始尝试下一个点
            book[tx][ty]=0;  //尝试结束，取消这个点的标记 
        } 
    }
    return;
} 

int main()
{
    int i,j,startx,starty;
    scanf("%d %d",&n,&m);  //读入n和m，n为行，m为列
    /*读入迷宫*/
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    scanf("%d %d %d %d",&startx,&starty,&p,&q);  //读入起点和终点坐标
    /*从起点开始搜索*/
    book[startx][starty]=1;  //标记起点已经在路径中，防止后面重复走
    dfs(startx,starty,0);  //第一个参数是起点的x坐标，以此类推是起点的y坐标，初始步数为0
    printf("%d",min);  //输出最短步数
    return 0; 
}

 

然后又写了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[10][10];
int dir[5][2]={{0,1},{1,0},{0,-1},{-1,0},{0,0}},minn;
int judge(){
    char a=map[1][0];
    for(int i=0;i<4;++i){
        for(int j=0;j<4;++j){
            if(map[i][j]!=map[1][0])
            return 0;
        }
    }
    return 1;
}
void swap(int x,int y){
    for(int i=0;i<5;++i){
       int xx=dir[i][0]+x;
       int yy=dir[i][1]+y;
       if(xx>=4||yy>=4||xx<0||yy<0)
       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>16)
    return;        //超过步数 ，break 
    if(judge()){
    minn=minn>step?step:minn;          //维护最小值 
    }
    if(y>=4){
        x++;
        y=0;
    }
    if(x>=4){
        return;  //break;
    }
    for(int j=0;j<2;++j){
       if(j==1){
       swap(x,y);//换的情况 
       dfs(x,y+1,step+1);//按这个路子继续深搜 
       swap(x,y);//恢复原状 
   }
   else{
        dfs(x,y+1,step); //不翻； 
      }
    } 
  }
int main(void){
    minn=inf;
    for(int i=0;i<4;++i){
        scanf("%s",map[i]);
    }
    dfs(0,0,0); //从起点开始搜； 
    if(minn>16)//步数比总棋子还多，说明不可能实现全部转换 
    printf("Impossible\n");
    else{
        printf("%d\n",minn);
    }
    return 0;
}

这个代码好丑..但是复制上去就懒的删了..

和上一题差不多意思，因为一个点只会被翻一次，翻两次没有意义；

dfs(深度优先搜索)是两个搜索中先理解并使用的，其实就是暴力把所有的路径都搜索出来，它运用了回溯，保存这次的位置，深入搜索，都搜索完了便回溯回来，搜下一个位置，直到把所有最深位置都搜一遍，要注意的一点是，搜索的时候有记录走过的位置，标记完后可能要改回来；

2.bfs(宽度/广度优先搜索)，这个一直理解了思想，不会用，后面才会的，思想，从某点开始，走四面可以走的路，然后在从这些路，在找可以走的路，直到最先找到符合条件的，这个运用需要用到队列(queue)，需要稍微掌握这个才能用bfs；

这是网上找到的dfs与bfs的区别；

贴上一个bfs的板子

int visit[N][N]//用来记录走过的位置
int dir[4][2]={0,-1,0,1,-1,0,1,0};
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]=1;//走过的进行标记，以免重复
        rep(i,0,4)//做多次查找
        {
            tt=t;
            tt.x+=dir[i][0];tt.y+=dir[i][1];//这里的例子是向上下左右查找的
            if(如果这个位置符合条件)
            {
                tt.bits++;//步数加一
                v.push(tt); //把它推入队列，在后面的时候就可以用了
            }
        }
    }
}