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

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)

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

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

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

struct Node {
    int x, y, pre;
    Node(int _x = -1, int _y = -1, int _pre = -1):x(_x),y(_y),pre(_pre){}
} Nodes[100];

bool inside(int x, int y) {
    return x >= 0 && x < 5 && y >= 0 && y < 5;
}

void print(Node p) {
    if(p.pre != -1)
        print(Nodes[p.pre]);
    printf("(%d, %d)
", p.x, p.y);
}

int main() {
    for (int i = 0; i < 5; ++i) {      // read in
        for (int j = 0; j < 5; ++j)
            scanf("%d", &G[i][j]);
    }
    int head = 0, rear = 0;
    Nodes[rear++] = Node(0, 0);
    while(head < rear) {                 //bfs
        Node tmp = Nodes[head++];
        if(vis[tmp.x][tmp.y])
            continue;
        vis[tmp.x][tmp.y] = 1;
        if(tmp.x == 4 && tmp.y == 4)
            print(Nodes[head - 1]);
        for (int i = 0; i < 4; ++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 - 1);
            }
        }
    }
    return 0;
}