BFS-POJ-3984-迷宮問題

迷宮問題Time Limit:1000 MS Memory Limit:65536 K Total Submissions:11333 Accepted:6784 Description
2 D配列を定義します.
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つの迷路を表して、その中の1は壁を表して、0は歩くことができる道を表して、横に歩くか縦に歩くしかなくて、斜めに歩くことができなくて、プログラムに左上の角から右下の角までの最短のルートを探し出すように要求します.Input
1つ5× 5の2次元配列で、迷路を表します.データは一意の解を保証します.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保存経路でいいです.

//
//  main.cpp
//      -K-    
//
//  Created by     on 15/8/9.
//  Copyright (c) 2015     . All rights reserved.
//

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

using namespace std;

bool maze[6][6];
bool visit[6][6];

typedef struct node
{
    int x,y;
    struct node *pre;
}Node;

typedef struct queue
{
    int head,tail;
    Node data[50];
}Queue;

Queue q;
Node final,out[50];

void init_queue()
{
    q.head=0;
    q.tail=0;
}

bool empty_queue()
{
    if (q.head==q.tail) {
        return 0;
    }
    return 1;
}

void bfs()
{
    Node t;
    q.data[0].x=0;
    q.data[0].y=0;
    visit[0][0]=1;
    q.tail++;
    while (empty_queue()) {
        t=q.data[q.head];
        //       
        if (t.x==4 && t.y==4) {
            final=q.data[q.head];
            return;
        }
        //    
        if (t.x>0 && visit[t.x-1][t.y]==0 && maze[t.x-1][t.y]==0) {
            q.data[q.tail].x=t.x-1;
            q.data[q.tail].y=t.y;
            q.data[q.tail].pre=&q.data[q.head];
            q.tail++;
            visit[t.x-1][t.y]=1;
        }
        if (t.x<4 && visit[t.x+1][t.y]==0 && maze[t.x+1][t.y]==0) {
            q.data[q.tail].x=t.x+1;
            q.data[q.tail].y=t.y;
            q.data[q.tail].pre=&q.data[q.head];
            q.tail++;
            visit[t.x+1][t.y]=1;
        }
        if (t.y>0 && visit[t.x][t.y-1]==0 && maze[t.x][t.y-1]==0) {
            q.data[q.tail].x=t.x;
            q.data[q.tail].y=t.y-1;
            q.data[q.tail].pre=&q.data[q.head];
            q.tail++;
            visit[t.x][t.y-1]=1;
        }
        if (t.y<4 && visit[t.x][t.y+1]==0 && maze[t.x][t.y+1]==0) {
            q.data[q.tail].x=t.x;
            q.data[q.tail].y=t.y+1;
            q.data[q.tail].pre=&q.data[q.head];
            q.tail++;
            visit[t.x][t.y+1]=1;
        }
        q.head++;
    }
}

int main(int argc, const char * argv[]) {
    Node *p1,*p2;
    for (int i=0; i<5; i++) {
        for (int j=0; j<5; j++) {
            cin >> maze[i][j];
        }
    }
    bfs();
    p1=&final;
    int t=0;
    while (p1!=NULL) {
        p2=p1->pre;
        out[t].x=p1->x;
        out[t].y=p1->y;
        t++;
        p1=p2;
    }
    while (t--) {
        printf("(%d, %d)
",out[t].x,out[t].y);
    }
    return 0;
}