当前位置：网站首页>nyoj58 最少步数(DFS)

nyoj58 最少步数(DFS)

2022-08-09 08:10:00 【51CTO】

最少步数

3000 ms | 内存限制： 65535

这有一个迷宫，有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）分别表示起点的行、列，终点的行、列。

输出输出最少走几步。样例输入

样例输出

来源 [苗栋栋]原创

上传者苗栋栋

一道非常简单的深搜题。只要判断好是否出界就没什么难的了。。

       
       #include <stdio.h>
       
       int 
       
       s1,
       
       s2,
       
       min,
       
       e1,
       
       e2;
       
       int 
       
       a[
       
       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 
       
       s1,
       
       int 
       
       s2,
       
       int 
       
       step)
       
{
       
       if(
       
       s1
       
       <
       
       0
       
       ||
       
       s1
       
       >
       
       8
       
       ||
       
       s2
       
       <
       
       0
       
       ||
       
       s2
       
       >
       
       8
       
       ||
       
       a[
       
       s1][
       
       s2])
       
       //判断是否出界和能不能走
       
       return ;
       
       if(
       
       s1
       
       ==
       
       e1
       
       &&
       
       s2
       
       ==
       
       e2
       
       &&
       
       step
       
       <
       
       min)
       
       //找到终点，判断步数
       
       min
       
       =
       
       step;
       
       a[
       
       s1][
       
       s2]
       
       =
       
       1;
       
       dfs(
       
       s1
       
       +
       
       1,
       
       s2,
       
       step
       
       +
       
       1);
       
       dfs(
       
       s1
       
       -
       
       1,
       
       s2,
       
       step
       
       +
       
       1);
       
       dfs(
       
       s1,
       
       s2
       
       +
       
       1,
       
       step
       
       +
       
       1);
       
       dfs(
       
       s1,
       
       s2
       
       -
       
       1,
       
       step
       
       +
       
       1);
       
       a[
       
       s1][
       
       s2]
       
       =
       
       0;
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       t;
       
       scanf(
       
       "%d",
       
       &
       
       t);
       
       while(
       
       t
       
       --)
       
  {
       
       scanf(
       
       "%d %d %d %d",
       
       &
       
       s1,
       
       &
       
       s2,
       
       &
       
       e1,
       
       &
       
       e2);
       
       min
       
       =
       
       81;
       
       dfs(
       
       s1,
       
       s2,
       
       0);
       
       printf(
       
       "%d\n",
       
       min);
       
  }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15742657/5557840

当前位置：网站首页>nyoj58 最少步数(DFS)

nyoj58 最少步数(DFS)

最少步数

边栏推荐

猜你喜欢

随机推荐