在很久很久以前,有一位大师级程序员,实力高强,深不可测,代码能力无人能及。从来没有人听说过他的真名,只知道他在完成一段代码后,总会跟上一行注释“十四出品,必属精品”,于是他在编程江湖上便有了绰号“十四”。
随着十四大师声名远播,意图登门拜访,寻求编程秘法的人也渐渐多了起来。然而,正如他无人知晓的真名一般,十四大师的真面目也少有人得见。这并不是因为大师住处隐秘,而是因为大师居所前有着他亲自布下的阵法,它困住了无数虔诚的求知者。
作为十四大师崇拜者的小胖经过苦心探寻,终于有一天得到了法阵的地图。
地图显示,法阵是方形的,纵横皆为五里,在地图上简示为5*5的矩阵,且只由0或1组成。其中,0表示可以走的路,1表示阻止通行的屏障。左上角和右下角分别是阵的入口和出口,这两个位置的数字保证为0。
既然得到了地图,破解法阵自然不再是难事。现在,小胖不仅想要走出法阵,还想知道怎样才能用最短的路线走出法阵。
Input 输入是一个5 × 5的二维数组,仅由0、1两数字组成,表示法阵地图。
Output 输出若干行,表示从左上角到右下角的最短路径依次经过的坐标,格式如样例所示。数据保证有唯一解。
Sample Input 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
Sample Output (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)
Hint 坐标(x, y)表示第x行第y列,行、列的编号从0开始,且以左上角为原点。
另外注意,输出中分隔坐标的逗号后面应当有一个空格。
bfs求最短路径,加上一个路径记录。CLion有毒,编译错误了好几次,就是练的少,还懒,生气,醒来就12点了,这要少了多少时间,生气。
//// Created by sequin on 2/16/17.//#include <iostream>#include <queue>#include <cstring>using namespace std;int mv[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};int grp[5][5];bool vis[5][5];queue <pair<int, int> > q;pair <int , int> now;pair<int, int> path[5][5];void bfs(){ memset(vis, false, sizeof(vis)); while(!q.empty()) q.pop(); vis[0][0] = true; q.push(make_pair(0, 0)); while(!q.empty()){ pair <int, int> tmp = (pair<int, int> &&) q.front(); q.pop(); int x = tmp.first; int y = tmp.second; for (int i = 0; i < 4; ++i) { int xx = x + mv[i][0]; int yy = y + mv[i][1]; if(xx < 0 || yy < 0 || xx >= 5 || yy >= 5){ continue; } if(grp[xx][yy] == 1){ continue; } if(vis[xx][yy]){ continue; } vis[xx][yy] = true; now.first = xx; now.second = yy; q.push(make_pair(xx, yy)); path[x][y] = now; } } now.first = now.second = 0; while(now.first != 4 || now.second != 4){ PRintf("(%d, %d)/n", now.first, now.second); now = path[now.first][now.second]; } printf("(4, 4)/n");}int main(){ for (int i = 0; i < 5; ++i) { for (int j = 0; j < 5; ++j) { cin >> grp[i][j]; } } bfs();}新闻热点
疑难解答