关键词:
armer John一直努力让他的草地充满鲜美多汁的而又健康的牧草。可惜天不从人愿,他在植物大战人类中败下阵来。邪恶的乳草已经在他的农场的西北部份占领了一片立足之地。
草地像往常一样,被分割成一个高度为Y(1 <= y <= 100), 宽度尾X(1 <= x <= 100)的直角网格。(1,1)是左下角的格(也就是说坐标排布跟一般的X,Y坐标相同)。乳草一开始占领了格(Mx,My)。每个星期,乳草传播到已被乳草占领的格子四面八方的每一个没有很多石头的格(包括垂直与水平相邻的和对角线上相邻的格)。1周之后,这些新占领的格又可以把乳草传播到更多的格里面了。
Bessie想要在草地被乳草完全占领之前尽可能的享用所有的牧草。她很好奇到底乳草要多久才能占领整个草地。如果乳草在0时刻处于格(Mx,My),那么还在那个时刻它们可以完全占领入侵整片草地呢(对给定的数据总是会发生)?
草地由一个图片表示。"."表示草,而"*"表示大石。比如这个X=4, Y=3的例子。
....
..*.
.**.
如果乳草一开始在左下角(第1排,第1列),那么草地的地图将会以如下态势发展:
乳草会在4星期后占领整片土地。
输入
*第一行: 四个由空格隔开的整数: X, Y, Mx, My
*第2到第Y+1行: 数据的第y+1行由X个字符("."表示草地,"*"表示大石),描述草地的第(Y+2-y)行。
输出
一个单独的整数表示最后一个不是大石块的格子被乳草占领的星期数。
样例输入
4 3 1 1 .... ..*. .**.
样例输出
4
注意行列数和一般的搜索不一样,转换一下就好
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <vector> 8 #include <stack> 9 #include <queue> 10 #include <set> 11 #include <map> 12 #include <sstream> 13 const int INF=0x3f3f3f3f; 14 typedef long long LL; 15 using namespace std; 16 17 int n,m,sx,sy; 18 struct node 19 20 int x,y; 21 int step; 22 node() 23 node(int _x,int _y,int _step) x=_x; y=_y; step=_step; 24 ; 25 char G[105][105]; 26 int vis[101][101]; 27 int NT[8][2]=-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1,-1,-1; 28 29 void BFS() 30 31 memset(vis,0,sizeof(vis)); 32 queue<node> qe; 33 vis[sx][sy]=1; 34 qe.push(node(sx,sy,0)); 35 int ans=-1; 36 while(!qe.empty()) 37 38 node t; 39 t=qe.front(); 40 qe.pop(); 41 for(int i=0;i<8;i++) 42 43 int xx=t.x+NT[i][0]; 44 int yy=t.y+NT[i][1]; 45 if(xx>0&&xx<=n&&yy>0&&yy<=m&&!vis[xx][yy]&&G[xx][yy]==‘.‘) 46 47 qe.push(node(xx,yy,t.step+1)); 48 vis[xx][yy]=1; 49 ans=max(ans,t.step+1);//更新答案 50 51 52 53 printf("%d ",ans); 54 55 56 int main() 57 58 scanf("%d %d %d %d",&m,&n,&sy,&sx);//输入时换一下位置 59 sx=n-sx+1;//转换一下sx 60 for(int i=1;i<=n;i++) 61 scanf("%s",G[i]); 62 BFS(); 63 64 return 0; 65
-
unity草的制作(代码片段)
如果把草当成一个一个的模型的话,我们在一个平面上铺满10000个草并且让他和一些物体进行交互的,如果用传统的做法,我们把每一个草上面挂载一个脚本的话,运行的时候你就会发现,这样帧率其实并不高... 查看详情
区间分组stallreservations(代码片段)
题意(n)头牛,每头牛有一个开始吃草的时间和结束吃草的时间,当两头牛之间存在交点的时候,这两头牛不能安排在同一个畜栏吃草,求需要的最小畜栏数目和每头牛对应的畜栏方案贪心步骤:(1)将所有牛按开始吃草的时间... 查看详情
poj1475pushingboxes(bfs套bfs)(代码片段)
描述Imagineyouarestandinginsideatwo-dimensionalmazecomposedofsquarecellswhichmayormaynotbefilledwithrock.Youcanmovenorth,south,eastorwestonecellatastep.Thesemovesarecalledwalks.Oneoftheemptycellscontain 查看详情
leftmousebutton(bfs)(代码片段)
MinesweeperisaverypopularsmallgameinWindowsoperatingsystem.Theobjectofthegameistofindmines,andmarkthemout.Youmarkthembyclickingyourrightmousebutton.Thenyouwillplacealittleflagwhereyouthinkthemineis.Yo 查看详情
java二叉树bfs(代码片段)
1004(bfs)(代码片段)
描述Youaretrappedina3Ddungeonandneedtofindthequickestwayout!Thedungeoniscomposedofunitcubeswhichmayormaynotbefilledwithrock.Ittakesoneminutetomoveoneunitnorth,south,east,west,upordown.Youcannotmovediago 查看详情
graph133.clonegraphinthreeways(bfs,dfs,bfs(recursive))(代码片段)
Cloneanundirectedgraph.Eachnodeinthegraphcontainsalabelandalistofitsneighbors.OJ‘sundirectedgraphserialization:Nodesarelabeleduniquely.Weuse#asaseparatorforeachnode,and,asaseparatorfornodelabelandeach 查看详情
sticks(剪枝+bfs)(代码片段)
ProblemDescriptionGeorgetooksticksofthesamelengthandcutthemrandomlyuntilallpartsbecameatmost50unitslong.Nowhewantstoreturnstickstotheoriginalstate,butheforgothowmanystickshehadoriginallyandhowlongthey 查看详情
java图bfs.java(代码片段)
bfs队列(代码片段)
PlagueInc.isafamousgame,whichplayerdevelopvirustoruintheworld.JSZKCwantstomodelthisgame.Let‘sconsidertheworldhas N imesMN×M cities.Theworldhas NN rowsand MMcolumns.Thecityint 查看详情
findaway(两个bfs)(代码片段)
ProblemDescriptionPassayearlearninginHangzhou,yifenfeiarrivalhometownNingboatfinally.LeaveNingbooneyear,yifenfeihavemanypeopletomeet.EspeciallyagoodfriendMerceki.Yifenfei’shomeisatthecountryside 查看详情
bfs广度遍历代码模板(代码片段)
BFS广度遍历代码模板/**广度遍历代码模板*/publicclassTestBFSpublicList<List<Integer>>bsf(TreeNoderoot)//如果节点为空if(root==null)returnnull;List<List<Integer>>result=newArrayList<>();Queue& 查看详情
java使用bfs的bipartite(代码片段)
nightmareⅱ(双向bfs)(代码片段)
ProblemDescriptionLastnight,littleerriyuehadahorriblenightmare.Hedreamedthatheandhisgirlfriendweretrappedinabigmazeseparately.Moreterribly,therearetwoghostsinthemaze.Theywillkillthepeople.Nowlittleerr 查看详情
dungeonmaster(三维bfs)(代码片段)
题目链接:http://poj.org/problem?id=2251题目:DescriptionYouaretrappedina3Ddungeonandneedtofindthequickestwayout!Thedungeoniscomposedofunitcubeswhichmayormaynotbefilledwithrock.Ittakesoneminutetomoveoneunitno 查看详情
图的遍历(bfs)(代码片段)
...优先遍历的过程可以类比树的层序遍历广度优先遍历的伪代码BFS邻接矩阵//BFS-----广度优先遍历voidGraph::BFS() queue<DataType>q;//队列存储的是顶点信息 //外层for循环,检查是否每个节点都被访问过,防止存在节点未被访问... 查看详情
bfs与dfs模板总结(代码片段)
1.常规BFS模板最典型的BFS场景之一为二叉树的层次遍历。如果我们不需要得到当前层数,可以采用如下模板样式。whilequeuenotempty cur=queue.pop() visitcur fornodeincur.neighbors ifnodevalidandnotvisit queue.push(node)2.需要确定层数的BFS模板... 查看详情
1076forwardsonweibo[bfs][一般](代码片段)
1076 ForwardsonWeibo(30)(30 分)WeiboisknownastheChineseversionofTwitter.OneuseronWeibomayhavemanyfollowers,andmayfollowmanyotherusersaswell.Henceasocialnetworkisformedwithfollowersrelations.W 查看详情