广度搜索 - Page 3

「vijos1876」小岛的标号
描述Xiaodao是一位喜欢参加ACM比赛的孩子.所谓ACM比赛,是一种团队比赛.每一次比赛,每队需要由恰好三位选手组成.现在,Xiaodao希望组建一支新的队伍,在这之前,他需要知道每一位朋友有多少可能成为自己的好队友.他计划给每一位朋友做出一个等级标号.Xiaodao本人的等级标号为0.如果一位朋友曾经和Xiaodao组队参加过比赛,那么就标号为1.如果一位朋友并没有与Xiaodao组队参加过比赛,但是曾经与一位"与Xiaodao一起参加过比赛的...
02014年10月29日2,698广度搜索

NOIP2002子串变换
描述已知有两个字串A$,B$及一组字串变换的规则（至多6个规则）:A1$->B1$A2$->B2$规则的含义为：在A＄中的子串A1$可以变换为B1$、A2$可以变换为B2$…。例如：A$＝'abcd'　B$＝'xyz'变换规则为：‘abc’->‘xu’　‘ud’->‘y’　‘y’->‘yz’则此时，A$可以经过一系列的变换变为B$，其变换的过程为：‘abcd’->‘xud’->‘xy’->‘xyz’共进行了三次变换，使得A$变换为B$。格式输入格式第...
02014年10月21日3,266广度搜索
「BZOJ1102」[POI2007] 山峰和山谷Grz
DescriptionFGD小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。为了能够让他对他的旅程有一个安排，他想知道山峰和山谷的数量。给定一个地图，为FGD想要旅行的区域，地图被分为n*n的网格，每个格子(i,j)的高度w(i,j)是给定的。若两个格子有公共顶点，那么他们就是相邻的格子。（所以与(i,j)相邻的格子有(i−1,j−1),(i−1,j),(i−1,j+1),(i,j−1),(i,j+1),(i+1,j−1),(i+1,j),(i+1,j+1)）。我们定义一个格子的集合...
12014年10月18日4,417广度搜索
「NOIP模拟赛」大逃亡
给出数字N（1<=N<=10000），X（1<=x<=1000），Y（1<=Y<=1000）,代表有N个敌人分布一个X行Y列的矩阵上，矩形的行号从0到X-1,列号从0到Y-1再给出四个数字x1,y1,x2,y2,代表你要从点(x1,y1)移到(x2,y2)。在移动的过程中你当然希望离敌人的距离的最小值最大化，现在请求出这个值最大可以为多少,以及在这个前提下，你最少要走多少步才可以回到目标点。注意这里距离的定义为两点的曼哈顿距离，即某两个点的坐...
12014年10月4日3,974二分法,广度搜索
「BZOJ1098」[POI2007] 办公楼biu
DescriptionFGD开办了一家电话公司。他雇用了N个职员，给了每个职员一部手机。每个职员的手机里都存储有一些同事的电话号码。由于FGD的公司规模不断扩大，旧的办公楼已经显得十分狭窄，FGD决定将公司迁至一些新的办公楼。FGD希望职员被安置在尽量多的办公楼当中，这样对于每个职员来说都会有一个相对更好的工作环境。但是，为了联系方便起见，如果两个职员被安置在两个不同的办公楼之内，他们必须拥有彼此的电话号码...
02014年10月3日5,806深度搜索,链表,广度搜索
「BZOJ1632」[Usaco2007 Feb] Lilypad Pond
DescriptionFarmerJohn建造了一个美丽的池塘，用于让他的牛们审美和锻炼。这个长方形的池子被分割成了M行和N列(1≤M≤30;1≤N≤30)正方形格子的。某些格子上有惊人的坚固的莲花，还有一些岩石，其余的只是美丽，纯净，湛蓝的水。贝茜正在练习芭蕾舞，她从一个莲花跳跃到另一个莲花，当前位于一个莲花。她希望在莲花上一个一个的跳，目标是另一个给定莲花。她能跳既不入水，也不到一个岩石上。令门外汉惊讶的是，贝茜的每次的...
02014年10月3日3,900广度搜索
「NOIP模拟赛」栅栏迷宫
田野上搭建了一个黄金大神专用的栅栏围成的迷宫。幸运的是，在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是，所建造的迷宫是一个“完美的”迷宫：即你能从迷宫中的任意一点找到一条走出迷宫的路。给定迷宫的宽W(1<=W<=38)及长H(1<=H<=100)。2*H+1行，每行2*W+1的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数(就是从最“糟糕”的一点，走出迷宫的最少步...
02014年9月27日3,481广度搜索
「BZOJ3299」[USACO2011 Open] Corn Maze玉米迷宫
Description今年秋天，约翰带着奶牛们去玩玉米迷宫。迷宫可分成NxM个格子，有些格子种了玉米，种宥玉米的格子无法通行。迷宫的四条边界上都是种了玉米的格子，其屮只有一个格子没种，那就是出口。在这个迷宫里，有一些神奇的传送点6每个传送点由一对点组成，一旦走入传送点的某个结点，机器就会强制把你送到传送点的另一头去。所有的传送点都是双向的，如果你定到了另一头，机器也会把你送回来。奶牛在一个单位的时间内只能向相...
02014年8月30日3,907广度搜索
「BZOJ1644」[Usaco2007 Oct] Obstacle Course 障碍训练课
Description考虑一个NxN(1<=N<=100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的，它们被标记为了'x'。例如下图：..Bx..xxA....x..x.....x.. 贝茜发现自己恰好在点A处，她想去B处的盐块舔盐。缓慢而且笨拙的动物，比如奶牛，十分讨厌转弯。尽管如此，当然在必要的时候她们还是会转弯的。对于一个给定的牧场，请你计算从A到B最少的转弯次数。开始的时候，贝茜可以使面对任意一个方向。贝茜知道...
02014年7月27日2,910广度搜索
「JoyOI1577」泥泞的道路
描述Description公园中有n个景点，编号1~n，并由m条双向道路相连。由于昨天下雨，导致公园中的马路泥泞不堪，每条道路都有一个泥泞程度w。现有Q个游客依次向你求助，想从景点X走到景点Y，他希望找到一条道路，使得经过道路泥泞程度的最大值尽量小。你能设计一个在线算法，帮他们找到方案吗？输入格式InputFormat第一行两个正整数n和m，表示景点数和道路数。随后m行每行三个正整数x、y、w，用来描述一条道路，它连接x和y景点并...
02014年7月26日3,975广度搜索,树上倍增
「BZOJ1615」[Usaco2008 Mar] The Loathesome Hay Baler麻烦的干草打包机
DescriptionFarmerJohn新买的干草打包机的内部结构大概算世界上最混乱的了，它不象普通的机器一样有明确的内部传动装置，而是，N(2<=N<=1050)个齿轮互相作用，每个齿轮都可能驱动着多个齿轮。FJ记录了对于每个齿轮i，记录了它的3个参数：X_i，Y_i表示齿轮中心的位置坐标(-5000<=X_i<=5000;-5000<=Y_i<=5000)；R_i表示该齿轮的半径(3<=R_i<=800)。驱动齿轮的位置为0,0，并且FJ也知道最终的工...
02014年7月23日4,253广度搜索
「NOIP模拟赛」聪明的打字员
聪明的打字员(typer)阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为6的密码。当然，她希望输入的过程中敲击键盘的总次数越少越好。不幸的是，出于保密的需要，该部门用于输入密码的键盘是特殊设计的，键盘上没有数字键，而只有以下六个键：Swap0，Swap1，Up，Down，Left，Right。为了说明这6个键的用，我们先定义录入区的6个位置的编号，从左至右依次为l，2，3，4，5，6。下面列出每个键...
32014年7月8日2,727广度搜索