E - 广搜记录路径 基础

Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

Submit     

Description

定义一个二维数组： 

int maze[5][5] = {  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, };

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

0 1 0 0 00 1 0 1 00 0 0 0 00 1 1 1 00 0 0 1 0

Sample Output

(0, 0)(1, 0)(2, 0)(2, 1)(2, 2)(2, 3)(2, 4)(3, 4)(4, 4) 这应该是最简单的BFS了吧。不过我还是第一次做BFS记录路径的题目，不容易啊，终于会输出路径了，呵呵。 其实也蛮简单的，在node点中多开一个int型指针，记录由上一个扩展而来的位子，最后把记录输入进栈，后入先出，反转过来就好。

#include"iostream"#include"stack"using namespace std; int a[6][6]; int book[6][6]; struct node { int x; int y; int f; }; int nex[4][2]={ { 1,0},{ 0,1},{ -1,0},{ 0,-1}}; void BFS() { struct node que[50]; stack
       
        s; int head,tail; head=tail=1; struct node b,t; b.x=b.y=0; b.f=0; que[tail]=b; book[0][0]=1; tail++; while(head
        
         4||t.y>4) continue; if(a[t.x][t.y]==