FZOJ Problem 2150 Fire Game
Accept: 2185 Submit: 7670
Time Limit: 1000 mSec Memory Limit :
32768 KB
Problem Description
Fat brother and Maze are playing a kind of special (hentai) game on an N*M
board (N rows, M columns). At the beginning, each grid of this board is
consisting of grass or just empty and then they start to fire all the grass.
Firstly they choose two grids which are consisting of grass and set fire. As we
all know, the fire can spread among the grass. If the grid (x, y) is firing at
time t, the grid which is adjacent to this grid will fire at time t+1 which
refers to the grid (x+1, y), (x-1, y), (x, y+1), (x, y-1). This process ends
when no new grid get fire. If then all the grid which are consisting of grass is
get fired, Fat brother and Maze will stand in the middle of the grid and playing
a MORE special (hentai) game. (Maybe it’s the OOXX game which decrypted in the
last problem, who knows.)
You can assume that the grass in the board would never burn out and the empty
grid would never get fire.
Note that the two grids they choose can be the same.
Input
The first line of the date is an integer T, which is the number of the text
cases.
Then T cases follow, each case contains two integers N and M indicate the
size of the board. Then goes N line, each line with M character shows the board.
“#” Indicates the grass. You can assume that there is at least one grid which is
consisting of grass in the board.
1 <= T <=100, 1 <= n <=10, 1 <= m <=10
Output
For each case, output the case number first, if they can play the MORE
special (hentai) game (fire all the grass), output the minimal time they need to
wait after they set fire, otherwise just output -1. See the sample input and
output for more details.
Sample Input
3 3
.#.
###
.#.
3 3
.#.
#.#
.#.
3 3
...
#.#
...
3 3
###
..#
#.#
Sample Output
Case 2: -1
Case 3: 0
Case 4: 2
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<cstring>
using namespace std;
const int N_MAX = + ;
int N,M;
char field[N_MAX][N_MAX];
bool vis[N_MAX][N_MAX];
int dx[] = { -,,, };
int dy[] = { ,,-, };
queue<pair<int,int> >que;
int num[N_MAX][N_MAX]; int bfs(int x1,int y1,int x2,int y2) {//返回 烧完所有草需要的时间
memset(vis, , sizeof(vis));//记录走过的点
memset(num, , sizeof(num));//记录到达某点的时间
int Max=;
que.push(make_pair(x1,y1));
que.push(make_pair(x2, y2));
vis[x1][y1] = vis[x2][y2] = ;
while (!que.empty()) {
int xx=que.front().first;
int yy = que.front().second;
que.pop();
for (int i = ; i < ; i++) {
int x = xx + dx[i];
int y = yy + dy[i];
if (x >= && x < N&&y >= && y < M&&!vis[x][y]&&field[x][y] == '#') {
vis[x][y] = true;
que.push(make_pair(x, y));
num[x][y] = num[xx][yy]+;
if (Max < num[x][y])Max = num[x][y];
}
}
}
for (int i = ; i < N;i++)
for (int j = ; j < M; j++)
if (field[i][j] == '#'&&!vis[i][j]) {
Max = INT_MAX;
} return Max;
} int main() {
int T,number;
scanf("%d", &T);
int cs = ;
while (T--) {
number = ;
cs++;
scanf("%d%d",&N,&M);
memset(field, , sizeof(field));
for (int i = ; i < N;i++) {
for (int j = ; j < M;j++) {
scanf(" %c",&field[i][j]);
if (field[i][j] == '#')
number++;
}
}
if (number <= ) {//!!!!草坪数小于2不用搜索了
printf("Case %d: %d\n", cs, );
continue;
}
int min_time=INT_MAX;
for (int i = ; i < N*M;i++) {
int x1 = i / M; int y1 = i%M;
if (field[x1][y1] != '#')continue;
for (int j = i+; j < N*M;j++) {
int x2 = j / M; int y2 = j%M;
if (field[x2][y2] != '#')continue;
int tmp= bfs(x1, y1, x2, y2);
if (tmp < min_time)
min_time = tmp;
}
} if (min_time == INT_MAX)min_time = -;
printf("Case %d: %d\n",cs,min_time); }
return ;
}
最新文章
- HTTPS那些事(三)攻击实例与防御(转载)
- 解决window2012 IIS8 配置的网站无法下载exe文件的问题
- XH
- daterangepicker 双日历/格式化日期/日期限制minDate,maxDate
- css翻页样式
- JS来添加弹出层,并且完成锁屏
- Leetcode: Insert Delete GetRandom O(1)
- cojs 疯狂的粉刷匠 疯狂的斐波那契 题解报告
- 关于socket阻塞与非阻塞情况下的recv、send、read、write返回值(转载)
- ios7新特性3-Map Kit新特性
- 【POJ2699】The Maximum Number of Strong Kings(网络流)
- android开源应用(主要是博客上带有分析的)收集 【持续更新】
- 『Kruscal重构树 Exkruscal』
- 1、Qt Project之基本文件打开与保存
- Remove Duplicate Letters(Java 递归与非递归)
- 2016年,谁是最受欢迎的 Java EE 服务器?
- 洛谷P1938 找工就业
- Log4net的配置-按照日期+文件大小混合分割
- hashCode和equals方法的区别与联系
- javascript总结16:数组array12