20170907_poj3984

//
//  main.cpp
//  hdu1260
//
//  Created by Haoying Zhao on 17/9/6.
//  Copyright © 2017年 Haoying Zhao. All rights reserved.
//

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
using namespace std;

struct point {
    int x, y;
};

int a[6][6];
bool mark[6][6];
int pre[26];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
point que[26];

void print_point(int t) {
    if(pre[t] == -1) {
        printf("(%d, %d)\n",que[t].x,que[t].y);
        return;
    }
    print_point(pre[t]);
    printf("(%d, %d)\n",que[t].x,que[t].y);
}

int bfs(point s, point e) {
    memset(pre, -1, sizeof(pre));
    memset(mark, false, sizeof(mark));
    memset(que, 0, sizeof(que));
    int head = 0, tail = 1;
    que[head] = s;
    mark[s.x][s.y] = 1;
    while(head != tail) {
        for(int i = 0; i < 4; ++i) {
            int xx = que[head].x + dx[i];
            int yy = que[head].y + dy[i];
            if(xx < 0 || yy < 0 || xx >= 5 || yy >= 5 || mark[xx][yy] == 1 || a[xx][yy] == 1)
                continue;
            point t;
            t.x = xx;
            t.y = yy;
            que[tail] = t;
            pre[tail] = head;
            mark[xx][yy] = 1;
            if(xx == 4  && yy == 4) {
                print_point(tail);
                return true;
            }
            tail++;
        }
        head++;
    }
    return false;
}

int main() {
    
    for(int i = 0; i < 5; ++i)
        for(int j = 0; j < 5; ++j)
            cin >> a[i][j];
    point a,b;
    a.x = a.y = 0;
    b.x = b.y = 4;
    bfs(a,b);
    return 0;
}