POJ9384 迷宫（基金会BFS)

本文来源于：http://blog.csdn.net/svitter

称号：让你从(0, 0)走到（4,4)。而且输出路径。

输入数据：二位数组的迷宫；输出数据：路径；

题解：简单的BFS

注意：

1.去重；

2.墙不能走；

3.记录前一个节点

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int maze[6][6];
bool visit[5][5];

struct node
{
    node *pre;
    int i;
    int j;
    node(){}
    node(int a, int b, node*c):i(a), j(b), pre(c){}
};

//1.去重
//2.是否墙壁
//
inline bool judge(int i, int j, int temp)
{
    if(temp < 0 || temp > 4)
        return false;

    //i, j 能够通行，而且没有訪问过
    if(maze[i][j] != 1 && !visit[i][j])
        return true;

    return false;

}

void output(){}

int main()
{
    int i, j;
    for(i = 0; i < 5; i++)
        for(j = 0; j < 5; j++)
            scanf("%d", &maze[i][j]);

    node queue[1000];
    memset(visit, 0, sizeof(visit));

    int front , rear;
    front = rear = -1;
    node cur;
    int temp;
    queue[++rear] = node(4, 4, NULL);

    while(front != rear)
    {
        cur = queue[++front];
        i = cur.i;
        j = cur.j;
        if(i == 0 && j == 0)
            break;

        temp = cur.i+1;
        if(judge(temp, j, temp))
        {
            queue[++rear] = node(temp, j, &queue[front]);
            visit[temp][j] = 1;
        }

        temp = cur.j+1;
        if(judge(i, temp, temp))
        {
            queue[++rear] = node(i, temp, &queue[front]);
            visit[i][temp] = 1;
        }

        temp = cur.i-1;
        if(judge(temp, j, temp))
        {
            queue[++rear] = node(temp, j, &queue[front]);
            visit[temp][j] = 1;
        }

        temp = cur .j-1;
        if(judge(i, temp, temp))
        {
            queue[++rear] = node(i, temp, &queue[front]);
            visit[i][temp] = 1;
        }
    }

    node *tmp;
    tmp = &queue[front];

    while(tmp != NULL)
    {
        printf("(%d, %d)
", tmp->i, tmp->j);
        tmp = tmp->pre;
    }
    return 0;
}