简单广搜，迷宫问题(POJ3984)

题目链接：http://poj.org/problem?id=3984

解题报告：

1、设置node结构体，成员pre记录该点的前驱。

2、递归输出：

void print(int i)
{
    if(q[i].pre!=-1)
    {
        print(q[i].pre);
        printf("(%d, %d)
",q[i].x,q[i].y);
    }
}

int MAP[5][5];
int front=0;
int rear=1;

int mov[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

struct node{
    int x,y;
    int pre;///从左上角到右下角的每一个元素的，前一个元素的位置，即保存路径；
}q[100];

void print(int i)
{
    if(q[i].pre!=-1)
    {
        print(q[i].pre);
        printf("(%d, %d)
",q[i].x,q[i].y);
    }
}

void bfs(int x1,int y1)
{
    q[front].x=x1;
    q[front].y=y1;
    q[front].pre=-1;
    while(front<rear)
    {
        for(int k=0;k<4;k++)
        {
            int tx=q[front].x+mov[k][0];
            int ty=q[front].y+mov[k][1];
            if(tx<0||tx>4||ty<0||ty>4||MAP[tx][ty])
                continue;
            else
            {
                MAP[tx][ty]=1;
                q[rear].x=tx;
                q[rear].y=ty;
                q[rear].pre=front;
                rear++;
            }
            if(tx==4&&ty==4)
            {
                print(front);
                return ;
            }
        }
        front++;
    }
}

int main()
{
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            scanf("%d",&MAP[i][j]);
    printf("(%d, %d)
",0,0);
    bfs(0,0);
    printf("(%d, %d)
",4,4);
    return 0;
}