BZOJ 1656: [Usaco2006 Jan] The Grove 树木(神奇的bfs之射线法)

1656: [Usaco2006 Jan] The Grove 树木

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 143  Solved: 88
[Submit][Status][Discuss]

Description

The pasture contains a small, contiguous grove of trees that has no ‘holes’ in the middle of the it. Bessie wonders: how far is it to walk around that grove and get back to my starting position? She’s just sure there is a way to do it by going from her start location to successive locations by walking horizontally, vertically, or diagonally and counting each move as a single step. Just looking at it, she doesn’t think you could pass ‘through’ the grove on a tricky diagonal. Your job is to calculate the minimum number of steps she must take. Happily, Bessie lives on a simple world where the pasture is represented by a grid with R rows and C columns (1 <= R <= 50, 1 <= C <= 50). Here’s a typical example where ‘.’ is pasture (which Bessie may traverse), ‘X’ is the grove of trees, ‘*’ represents Bessie’s start and end position, and ‘+’ marks one shortest path she can walk to circumnavigate the grove (i.e., the answer): …+… ..+X+.. .+XXX+. ..+XXX+ ..+X..+ …+++* The path shown is not the only possible shortest path; Bessie might have taken a diagonal step from her start position and achieved a similar length solution. Bessie is happy that she’s starting ‘outside’ the grove instead of in a sort of ‘harbor’ that could complicate finding the best path.

牧场里有一片树林,林子里没有坑.
    贝茜很想知道,最少需要多少步能围绕树林走一圈,最后回到起点.她能上下左右走,也能走对角线格子.牧场被分成R行C列(1≤R≤50,1≤C≤50).下面是一张样例的地图,其中“.”表示贝茜可以走的空地,  “X”表示树林,  “*”表示起点.而贝茜走的最近的路已经特别地用“+”表示出来.
 
题目保证,最短的路径一定可以找到.

Input

* Line 1: Two space-separated integers: R and C

* Lines 2..R+1: Line i+1 describes row i with C characters (with no spaces between them).

    第1行输入R和C,接下来R行C列表示一张地图.地图中的符号如题干所述.

Output

* Line 1: The single line contains a single integer which is the smallest number of steps required to circumnavigate the grove.

    输出最少的步数.

Sample Input

6 7
…….
…X…
..XXX..
…XXX.
…X…
……*

Sample Output

13
思路:我的思路是错的。。就不说了。。这题太神辣。。。用来求解绕过某一区域的最短路。。做法是找一个点做一条平行于边界的射线(单向)到另一边界。
射线法大概就是:如果和多变形交了奇数次,就说明在多边形内部,否则在外部。
讲真。。还不是特别明白。。。感觉和计算几何比较有关系。。。

BZOJ 1646: [Usaco2007 Open]Catch That Cow 抓住那只牛 (BFS)

1646: [Usaco2007 Open]Catch That Cow 抓住那只牛

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 915  Solved: 441
[Submit][Status][Discuss]

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 <= 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting. * Walking: FJ can move from any point X to the points X-1 or X+1 in a single minute * Teleporting: FJ can move from any point X to the point 2*X in a single minute. If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

    农夫约翰被通知,他的一只奶牛逃逸了!所以他决定,马上幽发,尽快把那只奶牛抓回来.
    他们都站在数轴上.约翰在N(O≤N≤100000)处,奶牛在K(O≤K≤100000)处.约翰有
两种办法移动,步行和瞬移:步行每秒种可以让约翰从z处走到x+l或x-l处;而瞬移则可让他在1秒内从x处消失,在2x处出现.然而那只逃逸的奶牛,悲剧地没有发现自己的处境多么糟糕,正站在那儿一动不动.
    那么,约翰需要多少时间抓住那只牛呢?

Input

* Line 1: Two space-separated integers: N and K

    仅有两个整数N和K.

Output

* Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

    最短的时间.

Sample Input

5 17
Farmer John starts at point 5 and the fugitive cow is at point 17.

Sample Output

4

OUTPUT DETAILS:

The fastest way for Farmer John to reach the fugitive cow is to
move along the following path: 5-10-9-18-17, which takes 4 minutes.

大概是写得第一道bfs了。

BZOJ 1644: [Usaco2007 Oct]Obstacle Course 障碍训练课 (BFS,DP)

 

1644: [Usaco2007 Oct]Obstacle Course 障碍训练课

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 451  Solved: 226
[Submit][Status][Discuss]

Description

考虑一个 N x N (1 <= N <= 100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的,它们被标记为了’x’。例如下图:

. . B x .
. x x A .
. . . x .
. x . . .
. . x . .

贝茜发现自己恰好在点A处,她想去B处的盐块舔盐。缓慢而且笨拙的动物,比如奶牛,十分讨厌转弯。尽管如此,当然在必要的时候她们还是会转弯的。对于一个给定的牧场,请你计算从A到B最少的转弯次数。开始的时候,贝茜可以使面对任意一个方向。贝茜知道她一定可以到达。

Input

第 1行: 一个整数 N 行

2..N + 1: 行 i+1 有 N 个字符 (‘.’, ‘x’, ‘A’, ‘B’),表示每个点的状态。

Output

行 1: 一个整数,最少的转弯次数。

Sample Input

3
.xA

Bx.

Sample Output

2
思路:bfs.我一开始的错误做法是用优先队列,以转弯数为关键字。
但是实际上错的,因为到达同一个点可能之后到达的方法有更少的转弯数,但是在做bfs的时候,之前访问的节点已经被标记了,所以无法更新成更优的值。
正解是类似dp的做法。需要注意不需要vis数组标记。
用dir[x][y][i]表示从i方向到达x,y的需要转弯数。
初始dir[s.x][s.y][0..3]为0,其余为inf

然后更新的时候如果dir[fx][fy][i]=min(dir[x][y][j]+1) 当i!=j

dir[fx][fy][i]=min(dir[x][y][j]) 当i=j

 

 

BZOJ 1632: [Usaco2007 Feb]Lilypad Pond (BFS,dp)

1632: [Usaco2007 Feb]Lilypad Pond

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 496  Solved: 153
[Submit][Status][Discuss]

Description

Farmer John 建造了一个美丽的池塘,用于让他的牛们审美和锻炼。这个长方形的池子被分割成了 M 行和 N 列( 1 ≤ M ≤ 30 ; 1 ≤ N ≤ 30 ) 正方形格子的 。某些格子上有惊人的坚固的莲花,还有一些岩石,其余的只是美丽,纯净,湛蓝的水。 贝茜正在练习芭蕾舞,她从一个莲花跳跃到另一个莲花,当前位于一个莲花。她希望在莲花上一个一个的跳,目标是另一个给定莲花。她能跳既不入水,也不到一个岩石上。 令门外汉惊讶的是,贝茜的每次的跳跃像中国象棋的马一样:横向移动1,纵向移动2,或纵向移动1,横向移动2。贝茜有时可能会有多达8个选择的跳跃。 Farmer John 在观察贝茜的芭蕾舞联系,他意识到有时候贝茜有可能跳不到她想去的目的地,因为路上有些地方没有莲花。于是他想要添加几个莲花使贝茜能够完成任务。一贯节俭的Farmer John想添加最少数量的莲花。当然,莲花不能放在石头上。 请帮助Farmer John确定必须要添加的莲花的最少数量。在添加的莲花最少基础上,算出贝茜从起始点跳到目标点需要的最少的步数。最后,还要算出满足添加的莲花的最少数量时,跳跃最少步数的跳跃路径的条数。

Input

第 1 行: 两个整数 M , N

第 2..M + 1 行:第 i + 1 行,第 i + 1 行 有 N 个整数,表示该位置的状态: 0 为水; 1 为莲花; 2 为岩石; 3 为贝茜开始的位置; 4 为贝茜要去的目标位置.

Output

第 1 行: 一个整数: 需要添加的最少的莲花数. 如果无论如何贝茜也无法跳到,输出 -1.

第 2 行: 一个整数: 在添加的莲花最少基础上,贝茜从起始点跳到目标点需要的最少的步数。如果第1行输出-1,这行不输出。 第 3 行: 一个整数: 添加的莲花的最少数量时,跳跃步数为第2行输出的值的跳跃路径的条数 如果第1行输出-1,这行不输出。

Sample Input

4 8
0 0 0 1 0 0 0 0
0 0 0 0 0 2 0 1
0 0 0 0 0 4 0 0
3 0 0 0 0 0 1 0

Sample Output

2
6
2

输出说明

至少要添加2朵莲花,放在了’x’的位置。

0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0
0 x 0 0 0 2 0 1 0 0 0 0 0 2 0 1
0 0 0 0 x 4 0 0 0 0 x 0 x 4 0 0
3 0 0 0 0 0 1 0 3 0 0 0 0 0 1 0
贝茜至少要条6步,有以下两种方案

0 0 0 C 0 0 0 0 0 0 0 C 0 0 0 0
0 B 0 0 0 2 0 F 0 0 0 0 0 2 0 F
0 0 0 0 D G 0 0 0 0 B 0 D G 0 0
A 0 0 0 0 0 E 0 A 0 0 0 0 0 E 0

题意;一个n*m的maze,0是空,1是荷花,2是石头,出发地是3,每次跳象棋的马字步,只能走在荷花上,但是可以在水上添加荷花,问从3到4,在添加荷花数最少的前提下,添加的荷花数是多少,最少的步数是多少,以及在前面两个最少的前提下,有多少种路径。
思路:前两个好搞。。最后一个路径数难住我了。。没有写过这种。。一开始是想在bfs或者dfs一遍找路径,但是可能不同路径会经过相同的点,所以vis的标记会是个问题。。回溯呢。。?反正我是没搞出来。。
正解是用到了类似dp的思想。。具体可以看代码。
以及:一开始我是想添加一些节点的信息到结构体里。。但是发现那样写起来会很麻烦。。
所以这道题最好再开几个数组存储节点的额外信息。。。
还有路径数比较多,要记得开long long

BZOJ 1627: [Usaco2007 Dec]穿越泥地 (BFS)

1627: [Usaco2007 Dec]穿越泥地

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 624  Solved: 411
[Submit][Status][Discuss]

Description

清早6:00,Farmer John就离开了他的屋子,开始了他的例行工作:为贝茜挤奶。前一天晚上,整个农场刚经受过一场瓢泼大雨的洗礼,于是不难想见,FJ 现在面对的是一大片泥泞的土地。FJ的屋子在平面坐标(0, 0)的位置,贝茜所在的牛棚则位于坐标(X,Y) (-500 <= X <= 500; -500 <= Y <= 500)处。当然咯, FJ也看到了地上的所有N(1 <= N <= 10,000)个泥塘,第i个泥塘的坐标为 (A_i, B_i) (-500 <= A_i <= 500;-500 <= B_i <= 500)。每个泥塘都只占据了它所在的那个格子。 Farmer John自然不愿意弄脏他新买的靴子,但他同时想尽快到达贝茜所在的位置。为了数那些讨厌的泥塘,他已经耽搁了一些时间了。如果Farmer John 只能平行于坐标轴移动,并且只在x、y均为整数的坐标处转弯,那么他从屋子门口出发,最少要走多少路才能到贝茜所在的牛棚呢?你可以认为从FJ的屋子到牛棚总是存在至少一条不经过任何泥塘的路径。

Input

* 第1行: 3个用空格隔开的整数:X,Y 和 N

* 第2..N+1行: 第i+1行为2个用空格隔开的整数:A_i 和 B_i

Output

* 第1行: 输出1个整数,即FJ在不踏进泥塘的情况下,到达贝茜所在牛棚所需要 走过的最小距离

Sample Input

1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2

输入说明:

贝茜所在牛棚的坐标为(1, 2)。Farmer John能看到7个泥塘,它们的坐标分
别为(0, 2)、(-1, 3)、(3, 1)、(1, 1)、(4, 2)、(-1, 1)以及(2, 2)。
以下为农场的简图:(*为FJ的屋子,B为贝茜呆的牛棚)

4 . . . . . . . .
3 . M . . . . . .
Y 2 . . M B M . M .
1 . M . M . M . .
0 . . * . . . . .
-1 . . . . . . . .
-2-1 0 1 2 3 4 5

X

Sample Output

11

HINT

    约翰的最佳路线是:(0,0),(一1,0),(一2,0),(一2,1),(一2,2),(一2,3),(一2,4),(一1,4),(0,4),  (0,3),  (1,3),  (1,2).
思路:bfs,坐标有负数,整体平移500即可。

BZOJ1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场 (BFS)

 

1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 661  Solved: 292
[Submit][Status][Discuss]

Description

The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cows. He wonders how many guards he will need if he wishes to put one on top of each hill. He has a map supplied as a matrix of integers; the matrix has N (1 < N <= 700) rows and M (1 < M <= 700) columns. Each member of the matrix is an altitude H_ij (0 <= H_ij <= 10,000). Help him determine the number of hilltops on the map. A hilltop is one or more adjacent matrix elements of the same value surrounded exclusively by either the edge of the map or elements with a lower (smaller) altitude. Two different elements are adjacent if the magnitude of difference in their X coordinates is no greater than 1 and the magnitude of differences in their Y coordinates is also no greater than 1.

 

农夫JOHN的农夫上有很多小山丘,他想要在那里布置一些保镖(……)去保卫他的那些相当值钱的奶牛们。 他想知道如果在一座小山丘上布置一名保镖的话,他总共需要招聘多少名保镖。他现在手头有一个用数字矩阵来表示地形的地图。这个矩阵有N行(1 < N < = 100)和M列( 1 < M < = 70) 。矩阵中的每个元素都有一个值H_ij(0 < = H_ij < =10,000)来表示该地区的海拔高度。请你帮助他统计出地图上到底有多少个小山丘。 小山丘的定义是:若地图中一个元素所邻接的所有元素都比这个元素高度要小(或它邻接的是地图的边界),则该元素和其周围所有按照这样顺序排列的元素的集合称为一个小山丘。这里邻接的意义是:若一个元素与另一个横坐标纵坐标和它的横纵坐标相差不超过1,则称这两个元素邻接。 问题名称:guard 输入格式: 第一行:两个由空格隔开的整数N和M 第二行到第N+1行:第I+1行描述了地图上的第I行,有M个由空格隔开的整数:H_ij.

Input

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 describes row i of the matrix with M space-separated integers: H_ij

Output

* Line 1: A single integer that specifies the number of hilltops

Sample Input

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

Sample Output

3

HINT

   三个山丘分别是:左上角的高度为4的方格,右上角的高度为1的方格,还有最后一行中高度为2的方格.

Source

[Submit][Status][Discuss]

HOME Back\

 

 

题目的中文描述的数据范围有问题!

题目的中文描述的数据范围有问题!

题目的中文描述的数据范围有问题!

思路:BFS,我的做法是预处理所有“坏点”,也就是如果点(i,j)的相邻点中有比点(i,j)高的,那么点(i,j)就是坏点。

然后bfs的时候,对于存在一个坏点的联通块(只有数字相同的点能构成一个联通块)都标记成坏点。

然后用左上角开始做bfs…注意遇到坏点跳过但是不要直接标记访问,因为可能之后的点会用到之前的坏点标记自身。

然而因为数据范围有问题wa了好多次。。。

于是看了题解:

大概都是另一种做法(而且都加入了输入挂,不懂,怎么感觉这些人是互相抄的2333)

从最高的点开始做dfs,每次把不大于当前点高度的点都访问掉。。。算作一次访问。

访问次数就是答案。

想了下确实比较巧妙,比较好写,然而比我的写法要慢。

然而窝不懂为什么这种写法数组开小就是返回RE,而我的写法数组开销就是返回WA…

选区_049

 

我的做法(800ms,bfs):

 

 

网上题解的做法(940ms,dfs):

BZOJ 1611: [Usaco2008 Feb]Meteor Shower流星雨 (BFS)

 

1611: [Usaco2008 Feb]Meteor Shower流星雨

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1239  Solved: 537
[Submit][Status][Discuss]

Description

去年偶们湖南遭受N年不遇到冰冻灾害,现在芙蓉哥哥则听说另一个骇人听闻的消息: 一场流星雨即将袭击整个霸中,由于流星体积过大,它们无法在撞击到地面前燃烧殆尽, 届时将会对它撞到的一切东西造成毁灭性的打击。很自然地,芙蓉哥哥开始担心自己的 安全问题。以霸中至In型男名誉起誓,他一定要在被流星砸到前,到达一个安全的地方 (也就是说,一块不会被任何流星砸到的土地)。如果将霸中放入一个直角坐标系中, 芙蓉哥哥现在的位置是原点,并且,芙蓉哥哥不能踏上一块被流星砸过的土地。根据预 报,一共有M颗流星(1 <= M <= 50,000)会坠落在霸中上,其中第i颗流星会在时刻 T_i (0 <= T_i <= 1,000)砸在坐标为(X_i, Y_i) (0 <= X_i <= 300;0 <= Y_i <= 300) 的格子里。流星的力量会将它所在的格子,以及周围4个相邻的格子都化为焦土,当然 芙蓉哥哥也无法再在这些格子上行走。芙蓉哥哥在时刻0开始行动,它只能在第一象限中, 平行于坐标轴行动,每1个时刻中,她能移动到相邻的(一般是4个)格子中的任意一个, 当然目标格子要没有被烧焦才行。如果一个格子在时刻t被流星撞击或烧焦,那么芙蓉哥哥 只能在t之前的时刻在这个格子里出现。请你计算一下,芙蓉哥哥最少需要多少时间才能到 达一个安全的格子。

Input

* 第1行: 1个正整数:M * 第2..M+1行: 第i+1行为3个用空格隔开的整数:X_i,Y_i,以及T_i

Output

输出1个整数,即芙蓉哥哥逃生所花的最少时间。如果芙蓉哥哥无论如何都无法在流星雨中存活下来,输出-1

Sample Input

4
0 0 2
2 1 2
1 1 2
0 3 5
输入说明:
一共有4颗流星将坠落在霸中,它们落地点的坐标分别是(0, 0),(2, 1),(1, 1)
以及(0, 3),时刻分别为2,2,2,5。

Sample Output

5

HINT

样例图示

题意:会有m颗流行,第i颗流行会在t[i]时刻砸到(x[i],y[i])点,砸到的点以及其相邻的四个点都会被烧焦。一个人从(0,0)出发,每次只能走到相邻的四个格子,并且只能走没有被烧焦的格子。问最少要多久才能走到一个安全的地方。
思路:bfs…先用一个数组star[x][y]表示格子(x,y)被烧焦的时间,初始为inf,表示没有被烧焦。
WA了两发。需要注意的是,一个格子可能多次被流星烧焦,烧焦的时间要取最小值。
以及,大概出题人的数学不怎么样?这题中描述的第一象限是包含x,y的正半轴以及原点的。

bzoj 1602: [Usaco2008 Oct]牧场行走 (bfs,优先队列)

Description

N头牛(2<=n<=1000)别人被标记为1到n,在同样被标记1到n的n块土地上吃草,第i头牛在第i块牧场吃草。 这n块土地被n-1条边连接。 奶牛可以在边上行走,第i条边连接第Ai,Bi块牧场,第i条边的长度是Li(1<=Li<=10000)。 这些边被安排成任意两头奶牛都可以通过这些边到达的情况,所以说这是一棵树。 这些奶牛是非常喜欢交际的,经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。

Input

*第一行:两个被空格隔开的整数:N和Q

*第二行到第n行:第i+1行有两个被空格隔开的整数:AI,BI,LI

*第n+1行到n+Q行:每一行有两个空格隔开的整数:P1,P2,表示两头奶牛的编号。

Output

*第1行到第Q行:每行输出一个数,表示那两头奶牛之间的距离。

Sample Input

4 2

2 1 2

4 3 2

1 4 3

1 2

3 2

Sample Output

2

7

 

思路:直接bfs….貌似因为每个点最多只和两个边相连。。。不用优先队列也行?
1A,好爽23333.

bc #77 ||hdu 5652 India and China Origins (图的动态连通性问题,并查集or 二分+bfs验证连通性)

题目链接
题意:没图不好描述,有中文题面中文题面,直接看吧。
思路:据说这道题有三种做法。 当时比赛一种都不会。

先说一种:做法是把格子看成点,可以到达的相邻格子之间看成有边相连,然后倒过来用并查集判断无向图的连通性。具体做法是:先统计初始所有空的位置,然后把所有要增加的山都加上(先统计空的位置是因为山之后要去掉,而去掉以后要得到该点的标号),然后将把所有空的点以及china(设标号为n*m+1)点,和india(设标号为n*m+2) 点通过并查集来合并..可以从上往下从左往右,每次只需要判断上面的点和左边的点是否有空,如果有就用并查集合并。 china点和india点特殊搞就好。

然后判断india和china是否联通,如果是则输出-1.否则从最后添加的山开始移除,每次移除一座山,添加四个方向能添加的边(注意这里不要忘记如果改点在第0行或者第n-1行还要添加和china或者india的边)

然后移除后询问india和china是否联通 (root(china)==root(india)?)

如果时间i联通了,而i+1没有联通,说明时间i是两国最早的失去联系的时间。

 

第一次做这种题目,这种题目的一般做法都是倒过来做。貌似还有一个二分删除的山+bfs判断连通性的。。。? 窝再搞搞看。
update :二分+bfs判断连通性。其实这个思路更常规。。做法就是字面意思。注意无解的判断即可。

 

并查集解法:

 

 

二分+bfs判断连通性。

codeforces 520 B. Two Buttons (bfs)

做过一道类似的题

因为是问最短,很容易想到是bfs

对于点x,可以到达点x-1,和点2*x

需要注意的是上界限。

并不是max(m,n)

因为可能先达到比m大,之后再减回来的情况是更优的。

max(2*m,2*n)肯定是足够的

poj 2688 Cleaning Robot (tsp问题)

______

好蠢,竟然没看出来这道题的不同之处,以为就是个搜

然后样例什么的都过了...

结果显然wa…

然后才发现,这道题应该是tsp问题.

解法是先跑一遍bfs,

对于所有的脏点和起点,得到没两个点之间的距离.

然后跑一遍dfs,枚举出所有的组合,同时更新答案.

晚安.

I – Fire Game (两个点开始的bfs)

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83084#problem/I
I – Fire Game

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit Status

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

4 3 3
.#.
###
.#.
3 3
.#.
#.#
.#.
3 3
#.#
3 3
###
..#
#.#
 

Sample Output

Case 1: 1
Case 2: -1
Case 3: 0
Case 4: 2
 
其实一开始是没什么思路的….因为要从两个点开始,太弱,没做过这样的.
然后我看了下数据,如果枚举着火的起点 10*10*10*10*100  10^6,再*bfs的时间复杂度…….
不过这是考虑所有点都是草的情况下,而且实际上枚举的时候两个点是无序的,只需要枚举一半就行…
虽然心里没什么底,我抱着写一发交上去试试tle掉又不会怀孕的心态写了下….
 
写的时候有两个地方卡了一下
一个是我不知道怎么表示两个点是同时烧的
bfs的时候万一写成了一个点都烧完,另一个点才开始烧,这肯定是错误的.
然后脑子里隐约记得什么控制步数blablabla,但是记得不清….
然后再一想,不用啊,两个点开始烧,我就把两个点初始化为0不就表示两个点开始烧了?
 
第二个地方小卡了一下,如果烧光,那答案是哪个点?
换句话说,哪个点的代价是最大的
显然是最后的那个点啊2333
然后写完了,交,竟然他妈过了….
喜极而泣!
好开心!

poj 3414 pots (bfs+路径记录)

Pots
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 11703   Accepted: 4955   Special Judge

Description

You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:

  1. FILL(i)        fill the pot i (1 ≤ ≤ 2) from the tap;
  2. DROP(i)      empty the pot i to the drain;
  3. POUR(i,j)    pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

Input

On the first and only line are the numbers AB, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).

Output

The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.

Sample Input

Sample Output

 

 

好爽,一遍ac