搜索学习（2）--NYOJ 58 最小步数

题目链接：click here 搜索入门题，

题意：给定一张8*8的图，给定两个坐标：起点和终点，规定0为可以走，1为墙，不能走，求出起点走到终点的最小步数。

dfs的基础应用

参考代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
int dir[4][2]= {{0,-1},{-1,0},{0,1},{1,0}};
const int maxn=10000;
const double eps = 1e-6;
const double Pi = acos(-1.0);
const int Inf=0xffff;
double mid,right;
int T,a1,a2,b1,b2,cc;
int maap[9][9]= {   1,1,1,1,1,1,1,1,1,
                    1,0,0,1,0,0,1,0,1,
                    1,0,0,1,1,0,0,0,1,
                    1,0,1,0,1,1,0,1,1,
                    1,0,0,0,0,1,0,0,1,
                    1,1,0,1,0,1,0,0,1,
                    1,1,0,1,0,1,0,0,1,
                    1,1,0,1,0,0,0,0,1,
                    1,1,1,1,1,1,1,1,1
                };
void dfs(int x,int y,int s)
{
    if(maap[x][y])     return;
    if(x==b1&&y==b2)       //如果是到达目的地，,搜索结束，比较最小的路径
    {
        cc=Min(s,cc);
        return;
    }
    s++;                   //每走一步，路径累加
    maap[x][y]=1;          //访问了,不在访问
    dfs(x+1,y,s);
    dfs(x,y+1,s);
    dfs(x-1,y,s);
    dfs(x,y-1,s);
    maap[x][y]=0;
}
int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        cc=Inf;
        scanf("%d%d%d%d",&a1,&a2,&b1,&b2);
       // printf("%d\n",cc);
        dfs(a1,a2,0);
        printf("%d\n",cc);
    }
    return 0;
}

搜索学习（2）--NYOJ 58 最小步数

原文：http://blog.csdn.net/u013050857/article/details/42806859