广度搜索 - Page 4

「BZOJ1656」[Usaco2006 Jan] The Grove 树木
DescriptionThepasturecontainsasmall,contiguousgroveoftreesthathasno'holes'inthemiddleoftheit.Bessiewonders:howfarisittowalkaroundthatgroveandgetbacktomystartingposition?She'sjustsurethereisawaytodoitbygoingfromherstartlocationtosuccessivelocationsbywalkinghorizontally,vertically,ordiagonallyandcountingeachmoveasasinglestep.Justlookingatit,shedoesn'tthinkyoucouldpass'through'thegroveonatrickyd...
02014年7月5日3,524广度搜索

「NOIP模拟赛」密码锁
题目描述hzwer有一把密码锁，由N个开关组成。一开始的时候，所有开关都是关上的。当且仅当开关x1,x2,x3,...xk为开，其他开关为关时，密码锁才会打开。他可以进行M种的操作，每种操作有一个size[i]，表示，假如他选择了第i种的操作的话，他可以任意选择连续的size[i]个格子，把它们全部取反。（注意，由于黄金大神非常的神，所以操作次数可以无限>_<）本来这是一个无关紧要的问题，但是，黄金大神不小心他的钱丢进去了，没有...
42014年6月1日5,293费用流,广度搜索,状压动规,记忆化搜索
「NOIP模拟赛」水灾
http://218.5.5.242:9018/JudgeOnline/problem.php?id=1452题目描述大雨应经下了几天雨，却还是没有停的样子。土豪CCY刚从外地赚完1e元回来，知道不久除了自己别墅，其他的地方都将会被洪水淹没。CCY所在的城市可以用一个N*M(N,M<=50)的地图表示，地图上有五种符号：“.*XDS”。其中“X”表示石头，水和人都不能从上面经过。“.”表示平原，CCY和洪水都可以经过。“*”表示洪水开始地方（可能有多个地方开始...
02014年6月1日4,087广度搜索
「BZOJ1627」[Usaco2007 Dec] 穿越泥地
Description清早6：00，FarmerJohn就离开了他的屋子，开始了他的例行工作：为贝茜挤奶。前一天晚上，整个农场刚经受过一场瓢泼大雨的洗礼，于是不难想见，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<=50...
02014年5月23日3,118广度搜索
「JoyOI1234」bench与奔驰
背景Background公园里有个人在练开奔驰 - -!，但是总是撞在bench上 (众人曰：狼来了，快跑啊!)描述Description公园里的bench与奔驰都是无敌的，不会被撞坏。由于开奔驰的人比较"有特点"，总是向上下左右四个方向开，而且只会在撞到椅子之后改变方向(起步时除外) - -!现在他给你一张地图，上面标明他的位置、公园里的bench的位置和他想到达的位置，可能会有冲出地图的可能请你告诉他最少撞多少下才能到达目的地，并...
12014年5月16日2,922广度搜索
NOI2005聪聪和可可
DescriptionInput数据的第1行为两个整数N和E，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。第2行包含两个整数C和M，以空格分隔，分别表示初始时聪聪和可可所在的景点的编号。接下来E行，每行两个整数，第i+2行的两个整数Ai和Bi表示景点Ai和景点Bi之间有一条路。所有的路都是无向的，即：如果能从A走到B，就可以从B走到A。输入保证任何两个景点之间不会有多于一条路直接相连，且聪聪和可可之间必有...
02014年4月27日7,531广度搜索,概率与期望
「BZOJ1671」[Usaco2005 Dec] Knights of Ni 骑士
DescriptionBessieisinCamelotandhasencounteredastickysituation:sheneedstopassthroughtheforestthatisguardedbytheKnightsofNi.Inordertopassthroughsafely,theKnightshavedemandedthatshebringthemasingleshrubbery.Timeisoftheessence,andBessiemustfindandbringthemashrubberyasquicklyaspossible.Bessiehasamapofoftheforest,whichispartitionedintoasquaregridarrayedintheusualmanner,withaxesparalleltotheXa...
02014年4月16日3,369广度搜索
「BZOJ1687」[Usaco2005 Open] Navigating the City 城市交通
Description 由于牛奶市场的需求，奶牛必须前往城市，但是唯一可用的交通工具是出租车．教会奶牛如何在城市里打的．给出一个城市地图，东西街区E(1≤E≤40)，南北街区N(1≤N≤30).制作一个开车指南给出租车司机，告诉他如何从起点（用S表示）到终点（用E表示）．每一个条目用空格分成两部分，第一个部分是方向（N，E，S，W之一），第二个是一个整数，表示要沿着这个方向开几个十字路口．如果存在多条路线...
02014年4月15日3,272广度搜索
「BZOJ1646」[Usaco2007 Open] Catch That Cow 抓住那只牛
DescriptionFarmerJohnhasbeeninformedofthelocationofafugitivecowandwantstocatchherimmediately.HestartsatapointN(0<=N<=100,000)onanumberlineandthecowisatapointK(0<=K<=100,000)onthesamenumberline.FarmerJohnhastwomodesoftransportation:walkingandteleporting.*Walking:FJcanmovefromanypointXtothepointsX-1orX+1inasingleminute*Teleporting:FJcanmovefromanypointXtothepoint2*Xi...
02014年4月12日2,806广度搜索
「BZOJ1611」[Usaco2008 Feb] Meteor Shower流星雨
Description去年偶们湖南遭受N年不遇到冰冻灾害，现在芙蓉哥哥则听说另一个骇人听闻的消息：一场流星雨即将袭击整个霸中，由于流星体积过大，它们无法在撞击到地面前燃烧殆尽，届时将会对它撞到的一切东西造成毁灭性的打击。很自然地，芙蓉哥哥开始担心自己的安全问题。以霸中至In型男名誉起誓，他一定要在被流星砸到前，到达一个安全的地方（也就是说，一块不会被任何流星砸到的土地）。如果将霸中放入一个直角坐标系中，芙蓉哥...
02014年4月6日3,108广度搜索
「BZOJ2252」[2010BJ WC] 矩阵距离
Description 假设我们有矩阵,其元素值非零即1a11……a1m…………….an1…….anm 定义aij与akl之间的距离为D(aij,akl)=abs(i-k)+abs(j-L)Input输入文件的第一行为两个整数，分别代表n和m。接下来的n行，第i行的第j个字符代表aijOutput输出包含N行，每行M个用空格分开的数字，其中第i行第J个数字代表Min(D(aij,axy)1<=x<=N1<=y<m,且axy=1SampleInput34000100110110SampleOutput321021001001H...
02014年4月3日3,441广度搜索
「BZOJ2292」[POJ Challenge] 永远挑战
Description lqp18_31和1tthinking经常出题来虐ftiasch。有一天,lqp18_31搞了一个有向图,每条边的长度都是1。他想让ftiasch求出点1到点 N 的最短路。"水题啊。",ftiasch这么说道。所以1tthinking把某些边的长度增加了1（也就是说，每条边的长度不是1就是2）。现在，可怜的ftiasch要向你求助了。 Input 第1行，两个整数 N (1≤ N ≤105)和 M (1≤ M ≤106),点和边的数量。第2到 M +1行:三个整数...
02014年4月2日2,849广度搜索