[水题一道]连连跳

问题描述

小明很贪玩，总是找些小游戏玩儿，今天他看到了一个新的游戏--连连跳，游戏是在一个由nxm个单元格组成的矩形里进行，每个方格里有一个整数x，表示从该方格向上，向下，向左，向右能跳1<=y<=x个方格到达一个新的方格。游戏开始时，小明在矩形的左上角（1，1），他要跳到（n，m），要求小明的跳动次数最少，并输出跳的路径

输入

　　每组测试先给出2个正整数n，m（2<=n,m<=100）,接着有n行，每行有m个数，当n=m=0时，输入结束。

输出

　　每组测试输出小明最少需要跳几步才到达目的地。接着输出他依次经过哪些单元。每个单元输出占一行。

样例输入

3 3

1 1 1

4 1 1

3 3

1 1 1

0 0

样例输出

1 1

2 1

3 1

3 3

1 1

解题报告：

非常简单，用广搜就可以解决，直接上代码

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <memory.h>
 4 #define true 1
 5 #define false 0
 6 #define max 10100
 7 
 8 struct
 9 {
10     int x,y,step,pre;
11 }queue_type[max];
12 int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
13 int vis[max][max];
14 int map[105][105];
15 int route[max][2];
16 int n,m;
17 int flag;
18 
19 int main()
20 
21 {
22 
23     while (scanf("%d%d",&n,&m)&&(n||m))
24     {
25         int i,j;
26         int head,tail;
27         head=tail=0;
28         memset(vis,0,sizeof(vis));
29         for (i=0;i<n;i++)
30             for(j=0;j<m;j++)
31             {
32                 scanf("%d",&map[i][j]);
33             }
34         queue_type[head].x=1;
35         queue_type[head].y=1;
36         queue_type[head].step=0;
37         queue_type[head].pre=-1;
38         //head++;
39         vis[1][1]=1;
40         flag = true;
41         while ((tail<=head)&&!vis[n][m])
42         {
43             int tx = queue_type[tail].x;
44             int ty = queue_type[tail].y;
45             for (i=0;i<4&&flag;i++)
46                 for (j=0;j<map[tx][ty]&&flag;j++)
47                 {
48                     int tx_x = tx+dir[i][0]*j;
49                     int ty_y = ty+dir[i][1]*j;
50 
51                     if (tx_x>=n||ty_y>=m)
52                         break;
53                     if (tx_x>=0&&tx_x<n&&ty_y>=0&&ty_y<m&&!vis[tx_x][ty_y])
54                     {
55                         head++;
56                         queue_type[head].x=tx_x;
57                         queue_type[head].y=ty_y;
58                         queue_type[head].step = queue_type[tail].step+1;
59                         queue_type[head].pre=tail;
60                         vis[tx_x][ty_y]=1;
61                     }
62                     if (tx_x==n&&ty_y==m)
63                         flag = false;
64                 }
65             tail++;
66 
67         }
68         printf("%d
",queue_type[head].step);
69         int t=0;
70         //print the way
71         while (head>=0)
72         {
73             route[++t][0] = queue_type[head].x;
74             route[t][1] = queue_type[head].y;
75             head = queue_type[head].pre;
76         }
77 
78         for (i=t;i>=1;i--)
79         {
80             printf("%d %d
",route[i][0],route[i][1]);
81         }
82     }
83 
84     //printf("Hello world!
");
85     return 0;
86 }