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;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 姓名:冉乔琪~公司:天兴医药 【日精进打卡第※88※天】 【知~学习】 《六项精进》2遍 共292遍 《大学》2遍...
    小小新酱阅读 225评论 2 1
  • 气质是什么?像大家都熟知的主持人董卿,电视剧《我的前半生》里的唐晶,她们说话做事特别干练,衣服的着装也让人看着舒服...
    宁洁阅读 223评论 0 1
  • 儿童金钱观培养 一、让孩子知道钱是哪来的; 我们应该尽早让孩子知道:金钱是通过辛苦工作换来的,是付出劳动后的报酬。...
    狄晓先阅读 224评论 0 3
  • 到了现在我发现现在最难的不是去学习什么,而是下决心去学习什么,这也是我没有很好的提升我的执行力的原因之一。其实我应...
    我的成长路阅读 168评论 0 0
  • 3月底在浮图店辖区值班,天气尚冷,不停活动脚上有汗,停下来会冷。这就是基层。中午还要想辙吃饭,不能耽误工作。大家很...
    君子包阅读 267评论 2 7