南阳理工 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

 1 #include<cstdio>
 2 #define M 10000 
 3 int map[9][9]={
 4  1,1,1,1,1,1,1,1,1,
 5  1,0,0,1,0,0,1,0,1,
 6  1,0,0,1,1,0,0,0,1,
 7  1,0,1,0,1,1,0,1,1,
 8  1,0,0,0,0,1,0,0,1,
 9  1,1,0,1,0,1,0,0,1,
10  1,1,0,1,0,1,0,0,1,
11  1,1,0,1,0,0,0,0,1,
12  1,1,1,1,1,1,1,1,1
13  };
14  int x,y,ex,ey,ans,i;
15 int ax[4]={-1,1,0,0};　　//四个方向对应x,y的变化
16 int ay[4]={0,0,-1,1};
17 void f(int x,int y,int c)
18  {
19      int nx,ny,i;
20      if(x == ex && y == ey)
21      {
22          ans=c;
23      }
24      else
25      {
26          for(i = 0 ; i < 4 ; i++)
27          {
28              nx=x+ax[i];
29              ny=y+ay[i];
30              if(c+1 < ans && map[nx][ny] == 0)
31              {
32                  map[nx][ny]=1;
33                  f(nx,ny,c+1);
34                  map[nx][ny]=0;
35              }
36              
37          }
38      }
39 }
40 int main()
41 {
42     
43     int t;
44     scanf("%d",&t);
45     while(t--)
46     {
47         int c=0;
48         ans=M;
49         scanf("%d %d %d %d",&x,&y,&ex,&ey);
50         map[x][y]=1;
51         f(x,y,c);
52         printf("%d
",ans);
53         map[x][y]=0;
54     }
55 }

——将来的你会感谢现在努力的自己。

南阳理工 58 最少步数 （DFS)

描述

输入

输出

样例输入

样例输出

南阳理工 58 最少步数（DFS)