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

FZU-2150 Fire Game

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

简介FZU-2150 Fire Game
双BFS(不是两个一样的BFS)
两个点同时点火,火可以蔓延,烧光草最快时间
连通度低于2剪枝
坑:遇到的第一个双搜索题目,入坑第一步,后方高能.该题没了,不知道做的对不对.

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3+10;
const int inf = 0x3f3f3f3f;
int n, m;
int sx, sy;
int fx, fy;
char G[maxn][maxn];
int vst[maxn][maxn];
int Time[maxn][maxn];
int curT[maxn][maxn];
int step[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

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

bool check(int x, int y){
    if(x<0 || x>=n || y<0 || y>=m || vst[x][y])
        return false;
    return G[x][y] == '.';
}

bool onBorder(int x, int y){
    if(x == 0 || x == n-1 || y == 0 || y == m-1)
        return true;
    return false;
}

void bfs_fire(queue<Point> fireQ){
    queue<Point> q;
    while(!fireQ.empty()){
        q.push(fireQ.front());
        fireQ.pop();
    }
    while(!q.empty()){
        Point p = q.front();
        q.pop();
        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] = 1;
                Time[cur_x][cur_y] = Time[p.x][p.y] + 1;
                q.push(Point(cur_x, cur_y));
            }
        }
    }
}

void bfs(){
    queue<Point> q;
    q.push(Point(sx, sy));
    curT[sx][sy] = 0;
    vst[sx][sy] = 1;
    while(!q.empty()){
        Point p = q.front();
        q.pop();
        if(onBorder(p.x, p.y)){
            printf("%d\n", curT[p.x][p.y]+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)){
                if(curT[p.x][p.y] + 1 < Time[cur_x][cur_y]){
                    curT[cur_x][cur_y] = curT[p.x][p.y] + 1;
                    vst[cur_x][cur_y] = 1;
                    q.push(Point(cur_x, cur_y));
                }
            }
        }
    }
    printf("IMPOSSIBLE\n");
}

int main(){
    int t;
    ios::sync_with_stdio(false);
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j){
                vst[i][j] = 0;
                Time[i][j] = inf;
                curT[i][j] = 0;
            }
        queue<Point> q;
        for(int i = 0; i < n; ++i){
            scanf("%s", G[i]);
            for(int j = 0; j < m; ++j){
                if(G[i][j] == 'J'){
                    sx = i;
                    sy = j;
                }
                if(G[i][j] == 'F'){
                    vst[i][j] = 1;
                    Time[i][j] = 0;
                    q.push(Point(i, j));
                }
            }
        }
        bfs_fire(q);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                vst[i][j] = 0;
        bfs();
    }
    return 0;
}

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

很赞哦! ()

上一篇:POJ-3414 Pots

下一篇:UVA-11624 Fire

文章评论

站点信息

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

客服在线

QQ客服

客服微信扫码

服务时间

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