Day2-C-迷宫问题 -POJ3984

定义一个二维数组：

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

Sample Output

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

分析：简单的求路径BFS问题，用数组处理更好找路径，直接上代码：

const int dx[] = {, -, , };

const int dy[] = {, , , -};

int G[][], vis[][];

struct Node {

    int x, y, pre;

    Node(int _x = -, int _y = -, int _pre = -):x(_x),y(_y),pre(_pre){}

} Nodes[];

bool inside(int x, int y) {

    return x >=  && x <  && y >=  && y < ;

}

void print(Node p) {

    if(p.pre != -)

        print(Nodes[p.pre]);

    printf("(%d, %d)\n", p.x, p.y);

}

int main() {

    for (int i = ; i < ; ++i) {      // read in

        for (int j = ; j < ; ++j)

            scanf("%d", &G[i][j]);

    }

    int head = , rear = ;

    Nodes[rear++] = Node(, );

    while(head < rear) {                 //bfs

        Node tmp = Nodes[head++];

        if(vis[tmp.x][tmp.y])

            continue;

        vis[tmp.x][tmp.y] = ;

        if(tmp.x ==  && tmp.y == )

            print(Nodes[head - ]);

        for (int i = ; i < ; ++i) {

            int nx = tmp.x + dx[i], ny = tmp.y + dy[i];

            if(inside(nx,ny) && !G[nx][ny] && !vis[nx][ny]) {     //prevent multiple entries

                Nodes[rear++] = Node(nx, ny, head - );

            }

        }

    }

    return ;

}

巴特西

Day2-C-迷宫问题 -POJ3984

最新文章

热门文章