NYOJ 58 最少步数（深搜DFS）

本文主要是介绍NYOJ 58 最少步数（深搜DFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

这有一个迷宫，有0~8行和0~8列：

 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

0表示道路，1表示墙。

现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？

（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）

输入

第一行输入一个整数n（0<n<=100），表示有n组测试数据;
随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。

输出

输出最少走几步。

样例输入

2
3 1  5 7
3 1  6 7

样例输出

12
11

思路：

基础的的搜索题目，

两种搜索都可以。

DFS代码：

#include<cstdio>
#define MYDD 110300int sx,sy,ex,ey,ans;//起始和终点坐标,步数
int dx[4]= {-1,1,0,0};
int dy[4]= {0,0,-1,1}; //移动的方向
int map[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 c) {if(x==ex&&y==ey) {if(c<ans)ans=c;return ;}for(int j=0; j<4; j++) {int gx=x+dx[j];int gy=y+dy[j];if(map[gx][gy]==0&&c+1<ans) {map[gx][gy]=1;//访问过的节点置为墙DFS(gx,gy,c+1);//递归访问下一坐标map[gx][gy]=0;//	printf("************c: %d ****\n",c);}}
}int main() {int t;scanf("%d",&t);while(t--) {int c=0;//记录步数scanf("%d%d%d%d",&sx,&sy,&ex,&ey);map[sx][sy]=1;//起始坐标置为已经访问ans=MYDD;DFS(sx,sy,c);printf("%d\n",ans);map[sx][sy]=0;}return 0;
}

BFS代码：

#include<cstdio>
#include<cstring>
#include<queue>using namespace std;int map[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,
};int sx,sy,ex,ey;//开始和结束的坐标
int dx[]= {0,0,-1,1};
int dy[]= {-1,1,0,0}; //四个移动方向
bool vis[9][9];//访问标记数组struct Point {int x,y,step;//坐标和步数
};int BFS() {queue<Point> q;//定义 Point 类型队列Point temp;//定义临时结构体变量用于存储开始坐标temp.x=sx;temp.y=sy;temp.step=0;q.push(temp);while(!q.empty()) {Point dd=q.front();//取出队首元素给新定义的 结构体变量q.pop();//移去队首元素if(dd.x==ex&&dd.y==ey)return dd.step;for(int j=0; j<4; j++) {temp.x=dd.x+dx[j];temp.y=dd.y+dy[j];temp.step=dd.step+1;if(!map[temp.x][temp.y]&&vis[temp.x][temp.y])q.push(temp);vis[temp.x][temp.y]=false;}}
}int main() {int t;scanf("%d",&t);while(t--) {memset(vis,true,sizeof(vis));scanf("%d%d%d%d",&sx,&sy,&ex,&ey);int ans=BFS();printf("%d\n",ans);}return 0;
}

这篇关于NYOJ 58 最少步数（深搜DFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---