AutoPilot02（去哪儿2017校招真题）

题目描述

自动驾驶技术这个词因Tesla为人们所熟悉，殊不知tesla仍只是处于非常初级辅助阶段，然而Uber与Volvo已经开始在匹兹堡试验部署真正意义的自动驾驶汽车，原理是在构建好的复杂地图数据基础上，根据在车辆移动时通过GPS结合车上的数个传感器、立体摄像头以及激光雷达收集数据与地图数据比对以此来识别交通标志、行人和障碍物并选择合适的道路自动讲乘客从A点带到B点。假设我们将地图抽象成一个N x N的二维矩阵，0为可行驶道路1为障碍物，车辆只能一步步按东、南、西、北方向行驶，请编程找出一条从A点[0,0]至B点[n-1,n-1]的最短路径。

输入
一共n行，每行n个整数（空格分隔），只可能为0或1

样例输入
0 1 0 0
0 0 0 1
1 0 1 0
0 0 0 0

输出
输出最短路径，不可到达则输出nopath

样例输出
0,0
1,0
1,1
2,1
3,1
3,2
3,3

时间限制
C/C++语言：1000MS其它语言：3000MS 
内存限制
C/C++语言：65536KB其它语言：589824KB


标准的广度优先遍历算法。
#include #include #include using namespace std; typedef struct Dot{ int x; int y; struct Dot *next; struct Dot *before; } Dot; Dot *head, *rear; int main() { string s; getline(cin, s); int n = s.size() / 2 + 1; int matrix[n + 2][n + 2]; for(int i = 1; i <= n; i++) { matrix[1][i] = s.at(2 * (i - 1)) - 48; } for(int i = 2; i <= n; i++) { for(int j = 1; j <= n; j++) { cin >> matrix[i][j]; } } head = (Dot *)malloc(sizeof(Dot)); rear = head; Dot *ope = (Dot *)malloc(sizeof(Dot)); ope -> x = 1; ope -> y = 1; ope -> before = NULL; rear -> next = ope; rear = ope; bool flag = true; while(rear != head) { ope = head -> next; head = head -> next; if(ope -> x == n && ope -> y == n) { flag = false; while(ope -> before) { ope -> before -> next = ope; ope = ope -> before; } while(ope) { cout << ope -> x - 1 << "," << ope -> y - 1 << endl; ope = ope -> next; } break; } if(matrix[ope -> x - 1][ope -> y] == 0) { matrix[ope -> x - 1][ope -> y] = 1; Dot *add = (Dot *)malloc(sizeof(Dot)); add -> x = ope -> x - 1; add -> y = ope -> y; add -> before = ope; add -> next = NULL; rear -> next = add; rear = add; } if(matrix[ope -> x + 1][ope -> y] == 0) { matrix[ope -> x + 1][ope -> y] = 1; Dot *add = (Dot *)malloc(sizeof(Dot)); add -> x = ope -> x + 1; add -> y = ope -> y; add -> before = ope; add -> next = NULL; rear -> next = add; rear = add; } if(matrix[ope -> x][ope -> y - 1] == 0) { matrix[ope -> x][ope -> y - 1] = 1; Dot *add = (Dot *)malloc(sizeof(Dot)); add -> x = ope -> x; add -> y = ope -> y - 1; add -> before = ope; add -> next = NULL; rear -> next = add; rear = add; } if(matrix[ope -> x][ope -> y + 1] == 0) { matrix[ope -> x][ope -> y + 1] = 1; Dot *add = (Dot *)malloc(sizeof(Dot)); add -> x = ope -> x; add -> y = ope -> y + 1; add -> before = ope; add -> next = NULL; rear -> next = add; rear = add; } } if(flag) { cout << "nopath"; } }
说明：
所有测试数据正确率为33.333298563957214%！
可以尝试再次完善代码，并调试，争取全部AC通过




错误数据：
该数据运行时间：0ms
该数据占用最大内存：1692kb
该数据运行结果：答案错误 ( Wrong Answer(WA) )
输入：
0 0 1 0 0 0 1
1 0 1 0 1 0 0
0 0 1 0 0 1 0
0 1 1 1 0 1 0
0 0 0 0 0 1 0
0 1 1 0 1 1 0
0 0 1 0 1 0 0




您的输出：
0,0
0,1
1,1
2,1
2,0
3,0
4,0
4,1
4,2
4,3
4,4
3,4
2,4
2,3
1,3
0,3
0,4
0,5
1,5
1,6
2,6
3,6
4,6
5,6
6,6