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

本文主要是介绍搜索学习（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 最小步数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---