UVA11624(bfs)

题意:给一张图,有火源,有障碍物,剩下的是道路,火源在下一分钟能够让上下左右四个方向的道路也着火,告诉人的位置,问最短时间能逃出去的时间是多少;

思路:一个bfs用来求出所有的火源能蔓延到的地方,另一个bfs求最短路,本来我以为bfs只能求最短路;

超级源:有多个源头的时候,就把所有的都压进去,每个源头能蔓延到的地方都看作是新的源头,继续压进去,每个只能蔓延4个方向,直到空;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <queue>
  6 #include <algorithm>
  7 #include <vector>
  8 #include <cstring>
  9 #include <stack>
 10 #include <cctype>
 11 #include <utility>
 12 #include <map>
 13 #include <string>
 14 #include <climits>
 15 #include <set>
 16 #include <string>
 17 #include <sstream>
 18 #include <utility>
 19 #include <ctime>
 20 using namespace std;
 21 const int MAXN(1010);
 22 const int MAXM(1000010);
 23 int fire[MAXN][MAXN];
 24 char g[MAXN][MAXN];
 25 bool vis[MAXN][MAXN];
 26 int fx[MAXM], fy[MAXM];
 27 int R, C, SX, SY;
 28 struct NODE
 29 {
 30     int x, y, val;
 31     NODE()
 32     {}
 33     NODE(int tx, int ty, int td): x(tx), y(ty), val(td)
 34     {}
 35 };
 36
 37 int ok(int nx,int ny)
 38 {
 39     if(nx >= 1 && nx <= R && ny >= 1 && ny <= C )
 40         return 1;
 41     return 0;
 42 }
 43 int move_x[4] = {0, -1, 0, 1};
 44 int move_y[4] = {-1, 0, 1, 0};
 45
 46 void bfs1(int n)///多个起点,超级源
 47 {
 48     queue<NODE> q;
 49     memset(fire+1, -1, sizeof(fire));
 50     for(int i = 0; i < n; ++i)///起点都压进去
 51     {
 52         q.push(NODE(fx[i], fy[i], 0));
 53         fire[fx[i]][fy[i]] = 0;
 54     }
 55     NODE cur;
 56     while(!q.empty())
 57     {
 58         cur = q.front();///从一个起点开始,然后四个方向扩散
 59         q.pop();
 60         for(int i = 0; i < 4; ++i)
 61         {
 62             int nx = cur.x+move_x[i], ny = cur.y+move_y[i];
 63             if(ok(nx,ny)&& g[nx][ny] != ‘#‘ && fire[nx][ny] == -1)
 64             {
 65                 fire[nx][ny] = cur.val+1;
 66                 q.push(NODE(nx, ny, cur.val+1));
 67                 ///重新做一个新的起点
 68             }
 69         }
 70     }
 71 }
 72
 73 int bfs2()
 74 {
 75     queue<NODE> q;
 76     memset(vis+1, false, sizeof(vis[0])*R);
 77     q.push(NODE(SX, SY, 0));
 78     vis[SX][SY] = true;
 79     NODE cur;
 80     while(!q.empty())
 81     {
 82         cur = q.front();
 83         q.pop();
 84         if(cur.x == 1 || cur.y == 1 || cur.x == R || cur.y == C)
 85             return cur.val+1;
 86         for(int i = 0; i < 4; ++i)
 87         {
 88             int nx = cur.x+move_x[i], ny = cur.y+move_y[i];
 89             if(ok(nx,ny)&& g[nx][ny] != ‘#‘ && !vis[nx][ny] && (fire[nx][ny] == -1 || cur.val+1 < fire[nx][ny]))
 90             {
 91                 vis[nx][ny] = true;
 92                 q.push(NODE(nx, ny, cur.val+1));
 93             }
 94         }
 95     }
 96     return -1;
 97 }
 98
 99 int main()
100 {
101     int T;
102     scanf("%d", &T);
103     while(T--)
104     {
105         scanf("%d%d", &R, &C);
106         int count = 0;
107         for(int i = 1; i <= R; ++i)
108         {
109             scanf("%s", g[i]+1);
110             for(int j = 1; j <= C; ++j)
111             {
112                 if(g[i][j] == ‘J‘)
113                 {
114                     SX = i;
115                     SY = j;
116                 }
117                 if(g[i][j] == ‘F‘)
118                 {
119                     fx[count] = i;
120                     fy[count++] = j;
121                 }
122             }
123         }
124         bfs1(count);
125         int ans = bfs2();
126         if(ans == -1)
127             printf("IMPOSSIBLE\n");
128         else
129             printf("%d\n", ans);
130     }
131     return 0;
132 }

时间: 05-11

UVA11624(bfs)的相关文章

pots(BFS)

D - Pots Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu Submit Status Description You are given two pots, having the volume of A and B liters respectively. The following operations can be performed: Input On the first and

USACO抓牛catchcow (bfs)

这题是黄巨大出的比赛题. http://poj.org/problem?id=3278 Description Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤

hdu 1728 逃离迷宫 (BFS)

逃离迷宫 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 14376    Accepted Submission(s): 3458 Problem Description 给定一个m × n (m行, n列)的迷宫,迷宫中有两个位置,gloria想从迷宫的一个位置走到另外一个位置,当然迷宫中有些地方是空地,gloria可以穿越,有些地方

牛汇(BFS)入金具体流程(图文指导)

牛汇开户流程:bfsforex牛汇入金教程 所谓入金,也就是充值的意思,必须充钱到平台才能进行外汇交易.首先,我们先登录bfsforex牛汇官方网站,在交易办公室功能区域下面,点击账户入金: 为您提供中国各大银行的网银支付解决方案,支持人民币支付,和信用卡入金,入金是实时到账的. 牛汇(BFS)入金具体流程(图文指导),布布扣,bubuko.com

URAL 1930 Ivan&#39;s Car(BFS)

Ivan's Car Time limit: 1.5 secondMemory limit: 64 MB The world is in danger! Awful earthquakes are detected all over the world. Houses are destroyed, rivers overflow the banks, it is almost impossible to move from one city to another. Some roads are

【判重+广搜(bfs)】魔板

判重+广搜(bfs)]魔板 Time Limit: 1000MS Memory Limit: 32768KB Special Judge 有一个两行四列的魔板,每个格子里有一个1到8的数字(数字唯一),现在我们可以对魔板进行以下操作: 1.交换两行的数字. 2.将第一列移到第二列,第二列到第三列,第三列到第四列,第四列到第一列. 3.将中间四个数顺时针转一次. 现给你初始状态,我末状态请你用最小的步数将它从初始状态变到末状态. 输入: 前两行,每行4个数表示初状态. 后两行,每行4个数表示末状态

[LeetCode] Binary Tree Zigzag Level Order Traversal(bfs)

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree {3,9,20,#,#,15,7}, 3 / 9 20 / 15 7 return its zig

USACO Mother&amp;#39;s Milk(bfs)

a=9MvljJDNdls&S=milk3">题目请点我 题解: 水杯倒水的问题非常经典,套路也是一样的,bfs找出全部状态. 这道题的关键在于每次都应该进行六次的倒水尝试,细心一点.PS:三维数组表示状态真的非常方便. 代码实现: /* ID: eashion LANG: C++ TASK: milk3 */ #include <iostream> #include <cstdio> #include <cstdlib> #include &l

[C++]广度优先搜索(BFS)(附例题)

广度优先搜索(BFS)(附例题) 问题产生: Isenbaev是国外的一个大牛. 现在有许多人要参加ACM ICPC. 一共有n个组,每组3个人.同组的3个人都是队友. 大家都想知道自己与大牛的最小距离是多少. 大牛与自己的最小距离当然是0.大牛的队友和大牛的最小距离是1.大牛的队友的队友和大牛的最小距离是2--以此类推. 如果实在和大牛没有关系的只好输出undefined了. 第一行读入n.表示有n个组.1 ≤ n ≤ 100 接下来n行,每行有3个名字,名字之间用空格隔开.每个名字的开头都是