UVA - 11624 多点bfs [kuangbin带你飞]专题一

题意：某人身陷火场，总有k个点着火，着火点可向四周扩散，问此人能否逃离。

思路：可能有多个着火点，以这些着火点作为起点进行bfs，得到整个火场的最短距离，然后又以人所在坐标作为起点进行bfs，得到该人到达火场各点的最短距离。枚举边界点，如果人到达某边界点的最短距离小于最短着火点到达的距离，则说明该点可以作为逃生的出口。

该题需要注意的地方：

1.可能没有着火点。我在这里WA了

对于这种数据：

4 4

FFFF

####

.J.#

....

答案： 2

但是我的AC代码对于这种情况无法得到正确答案，说明该题测试数据没有考虑这个数据。赤果果的不严谨啊！

解决这种情况的办法就是全部初始化为一个极大的数inf，将答案ans设置为 10^6 < ans < inf就可以得到正确答案了。

贴上有BUG的AC代码

#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int maxn = 1000 + 5;
char G[maxn][maxn];
int d[2][maxn][maxn];
int n, m;

struct node{
	int x, y;
	node(){
	}
	node(int x, int y):x(x), y(y){
	}
};

vector<node>fire;

const int dx[] = {0,0,-1,1};
const int dy[] = {1,-1,0,0};

void bfs(int c) {
	queue<node>q;
	for(int i = 0; i < fire.size(); ++i) {
	 	int x = fire[i].x, y = fire[i].y;
	 	d[c][x][y] = 0;
	 	q.push(node(x, y));
	}
	while(!q.empty()) {
		node p = q.front();
		q.pop();
		int x = p.x, y= p.y;
		for(int i = 0; i < 4; ++i) {
			int px = x + dx[i], py = y + dy[i];
			if(px < 0 || py < 0 || px >= n || py >= m) continue;
			if(G[px][py] == '#' || d[c][px][py] != -1) continue;
			d[c][px][py] = d[c][x][y] + 1;
			q.push(node(px, py));
		}
	}
}

int main() {
	int T;
	scanf("%d", &T);
	while(T--) {
		scanf("%d%d", &n, &m);
		for(int i = 0; i < n; ++i) scanf("%s", G[i]);

		int x, y;
		for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j) {
			if(G[i][j] == 'F') fire.push_back(node(i, j));
			if(G[i][j] == 'J') {
				x = i, y = j;
			}
		}
		int cnt = fire.size();
		memset(d, -1, sizeof(d));
		if(cnt) bfs(0);
		fire.clear();
		fire.push_back(node(x, y));
		bfs(1);
		int inf = 1 << 30;
		int ans = inf;

		// 枚举边界
		for(int i = 0; i < m ; ++i){
			if(cnt == 0) d[0][0][i] = d[0][n - 1][i] = inf + 1;
			if(d[1][0][i] < d[0][0][i] && G[0][i] != '#')
				ans = min(ans, d[1][0][i]);
			if(d[1][n - 1][i] < d[0][n - 1][i] && G[n - 1][i] != '#')
				ans = min(ans, d[1][n - 1][i]);
		}
		for(int i = 0; i < n; ++i) {
			if(cnt == 0) d[0][i][0] = d[0][i][m - 1] = inf + 1;
			if(d[1][i][0] < d[0][i][0] && G[i][0] != '#')
				ans = min(ans, d[1][i][0]);
			if(d[1][i][m - 1] < d[0][i][m - 1] && G[i][m - 1] != '#')
				ans = min(ans, d[1][i][m - 1]);
		}
		if(ans == inf) printf("IMPOSSIBLE\n");
		else printf("%d\n", ans + 1);
		fire.clear();
	}
	return 0;
}

如有不当之处欢迎指出！

随机推荐

Android SlidingMenu 仿网易新闻客户端布局
前面两篇文章中的SlidingMenu都出现在左侧,今天来模仿一下网易新闻客户端左右两边都有SlidingMenu的效果,以下是网易新闻客户端效果: 不扯闲话了,直接进入正题吧 frame_conte ...
tween&period;js
简要教程 tween.js是一款可生成平滑动画效果的js动画库.相关的动画库插件还有:snabbt.js 强大的jQuery动画库插件和Tweene-超级强大的jQuery动画代理插件. tween ...
form程序的界面修改
做主题视频库的界面的修改工作,是b/s端的窗口,是由form窗口生成,如下截图: 主要有三个方面,1.左侧菜单栏宽度固定,不随整个窗口大变化而变化.2.导出excel按钮的位置的移动,不管整个窗口是变 ...
React如何性能调优
一. 二.调优例子 <!DOCTYPE html> <html lang="zh-cn"> <head> <meta charset=&q ...
vim设置
折腾一下vim http://www.cnblogs.com/zhangsf/archive/2013/06/13/3134409.html
VC2008如何生成及使用DLL(完整版)
生成.使用DLL看起来简单,但做起来才发现还是有一些地方需要注意的. 1. 打开VS2008,新建一个VC工程,选择Win32类型,Win32项目: 2. 应用程序类型选择DLL,附加选项选择到处符号 ...
C&num;重的数组、集合（ArrayList）、泛型集合（list&lt&semi;T&gt&semi;）三者比较及扩展延伸……
本来我只想总结下数组.集合(ArrayList).泛型集合(list<T>)三者的比较的,可以一写下来要扩展的知识点有点多了,只能写一个小的知识点列表了如下: 1.数组.集合(ArrayL ...
JavaScript--我发现，原来你是这样的JS（再说引用类型，基本包装类型与个体内置对象）
一.介绍本篇是续上一篇的,引用类型的后篇,本篇主要是说基本包装类型和个体内置对象.如果你能收获一些知识,那我很高兴,很满足,哈哈哈,希望大家能愉快看完.如果你想学好一门技术,要不忘初心,方得始终. ...
[HNOI2010]MATRIX 矩阵
Description Input 第一行包含三个正整数N M P表示矩阵的行数列数以及每个数的范围,接下来N行每行包含M个非负整数,其中第i行第j个数表示以格子(i,j)为右下角的2*2子矩阵中的数 ...
abaqus2016安装过程中出现error&colon;unable to add abaqus command directory to PATH variable
请问abaqus2016安装过程中出现error:unable to add abaqus command directory to PATH variable是什么原因,怎么解决啊,总是安装失败这 ...

秒客网

UVA - 11624 多点bfs [kuangbin带你飞]专题一

随机推荐

相关文章