您现在的位置是:首页 > 学习之路 > ACM||算法ACM||算法

UVA-11624 Fire

卞振伟2019-07-25【ACM||算法】人已围观

简介UVA-11624 Fire
双BFS
一个迷宫,一个人,有起火处,火随时间蔓延,如果能逃离输出时间
深坑
1.原题描述火用的单数,并且没有指明有多个起火处,样例两个也都只有一个火,但是实际数据一个迷宫含多个火
2.前个BFS的结果对后BFS有影响,不能使用Point中声明变量d存BFS的深度来获取时间,改用二维数组存时间.
3.不同火可重复烧一个地方,但是到达的时间应取较小的
4.避免使用memset,改用for或者memset(sizeof(int)m*n

#include <iostream>
#include <queue>

using namespace std;

const int n = 5;
int step[][2]={{0,-1},{-1,0},{0,1},{1,0}};
int vst[100][100];
int mp[100][100];

bool check(int x,int y){
    if(x < 0 || x >= n || y < 0 || y >= n)
        return false;
    return true;
}

struct Point{
    int x, y;
    Point(int xx, int yy):x(xx), y(yy){}
    Point(){}
};


void bfs(){
    queue<Point> q;
    q.push(Point(0, 0));
    queue<string> qq;
    qq.push("00");
    while(!q.empty()){
        Point p = q.front();
        q.pop();
        string pp = qq.front();
        qq.pop();
        if(p.x == n-1 && p.y == n-1){
            for(int i = 0; i < pp.size(); i += 2){
                if(i)
                    cout<<endl;
                cout<<"("<<pp[i]<<", "<<pp[i+1]<<")";
            }
            return ;
        }
        for(int i = 0; i < 4; i++){
            int cur_x = p.x + step[i][0];
            int cur_y = p.y + step[i][1];
            if(check(cur_x,cur_y) && !vst[cur_x][cur_y] && !mp[cur_x][cur_y] ){
                vst[cur_x][cur_y] = 1;
                q.push(Point(cur_x, cur_y));
                string mo = pp + char(cur_x + '0') + char(cur_y + '0');
                qq.push(mo);
            }
        }
    }
}

int main(){
    for(int i = 0; i < n; i++)
        for(int j =0; j < n; j++){
            cin >> mp[i][j];
            vst[i][j] = 0;
        }
    vst[0][0] = 1;
    bfs();
}

Tags:ACM   编程   个人   题解   算法   C|C++

很赞哦! ()

上一篇:FZU-2150 Fire Game

下一篇:POJ-3984 迷宫问题

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:118篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00