问题描述
小明很贪玩，总是找些小游戏玩儿，今天他看到了一个新的游戏--连连跳，游戏是在一个由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
1 1 1
4 1 1
3 3
1 1 1
1 1 1
1 1 1
0 0
样例输出
3
1 1
2 1
3 1
3 3
0
1 1
解题思路：其实这道题非常简单，直接bfs, 不过需要打印路径。
1.先开一个路径数组way[205][2];
2.利用bfs里面的step。
#include <cstdio> #include <iostream> #include <queue> using namespace std; const int MAXN = 205; struct Dot{ int x; //横坐标 int y; //纵坐标 int step; //从起点到这个点的步数 }; int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0}; int map[MAXN][MAXN]; //迷宫 bool used[MAXN][MAXN]; //标记数组，如果这个点可以走的为true int way[MAXN][2]; //路线数组 保存从起点到终点的坐标 int BFS(Dot end) { queue<Dot> que; Dot start; start.x = start.y = 1; start.step = 0; used[1][1] = false; que.push(start); //把起点加入队列，然后开始宽搜 while (!que.empty()) { //如果队列为空就跳出 start = que.front(); //取出当前的坐标 que.pop(); way[start.step][0] = start.x; //把当前的坐标加入路线数组 way[start.step][1] = start.y; if (start.x == end.x && start.y == end.y) { //如果当前是终点的话 返回走的步数 return start.step; } Dot temp; for (int i = 0; i < 4; i++) { for (int j = map[start.x][start.y]; j >= 1; j--) { //当前点可以跳多少步，从大到小开始枚举走的路线 temp.x = start.x + dir[i][0] * j; temp.y = start.y + dir[i][1] * j; if (temp.x && temp.x <= end.x && temp.y && temp.y <= end.y) { if (used[temp.x][temp.y]) { //如果这步没走过就开始走 temp.step = start.step + 1; used[temp.x][temp.y] = false; //这步不能再走了 // cout << temp.step << endl; que.push(temp); } } } } } } int main(int argc, char const *argv[]) { int n, m; while (cin >> n >> m && n) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> map[i][j]; used[i][j] = true; } } Dot end; end.x = n; end.y = m; end.step = 0; int step = BFS(end); cout << step << endl; for (int i = 0; i <= step; i++) { cout << way[i][0] << " " << way[i][1] << endl; } } return 0; }
ps:因为不知道是不是OJ上的题，所以没办法提交验证对错，也就不知道写的对不对了。。。心累
