- 浏览: 35639 次
- 性别:
- 来自: 湖南
最新评论
-
kulinglei:
提烟而过 写道问下楼主:你是拿了别人的注册号在这里害别人,还是 ...
折半搜索 -
jy00105276:
没看代码,看描述难道是2分法?
是的话不一定是a[i-1] ...
折半搜索 -
提烟而过:
问下楼主:你是拿了别人的注册号在这里害别人,还是没事在这里装- ...
折半搜索 -
zqynux:
fffvvvzz 写道11-15
是
11 12 13 14 ...
折半搜索 -
zqynux:
额,, 就是一个NOIP题目的答案..
vijos 谁拿了最多奖学金
USACO 2.4 Overfencing 穿越栅栏
Overfencing
Kolstad and Schrijvers
Farmer John went crazy and created a huge maze of fences out in a field. Happily, he left out two fence segments on the edges, and thus created two "exits" for the maze. Even more happily, the maze he created by this overfencing experience is a `perfect' maze: you can find a way out of the maze from any point inside it.
Given W (1 <= W <= 38), the width of the maze; H (1 <= H <= 100), the height of the maze; 2*H+1 lines with width 2*W+1 characters that represent the maze in a format like that shown later - then calculate the number of steps required to exit the maze from the `worst' point in the maze (the point that is `farther' from either exit even when walking optimally to the closest exit). Of course, cows walk only parallel or perpendicular to the x-y axes; they do not walk on a diagonal. Each move to a new square counts as a single unit of distance (including the move "out" of the maze.
Here's what one particular W=5, H=3 maze looks like:
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+
Fenceposts appear only in odd numbered rows and and odd numbered columns (as in the example). The format should be obvious and self explanatory. Each maze has exactly two blank walls on the outside for exiting.
PROGRAM NAME: maze1
INPUT FORMAT
Line 1: W and H, space separated
Lines 2 through 2*H+2: 2*W+1 characters that represent the maze
SAMPLE INPUT (file maze1.in)
5 3
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+
OUTPUT FORMAT
A single integer on a single output line. The integer specifies the minimal number of steps that guarantee a cow can exit the maze from any possible point inside the maze.
SAMPLE OUTPUT (file maze1.out)
9
The lower left-hand corner is *nine* steps from the closest exit.
描述
农夫John在外面的田野上搭建了一个巨大的用栅栏围成的迷宫。幸运的是,他在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是,他所建造的迷宫是一个“完美的”迷宫:即你能从迷宫中的任意一点找到一条走出迷宫的路。给定迷宫的宽W(1<=W<=38)及长H(1<=H<=100)。 2*H+1行,每行2*W+1的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数(就是从最“糟糕”的一点,走出迷宫的最少步数)。(即使从这一点以最优的方式走向最靠近的出口,它仍然需要最多的步数)当然了,牛们只会水平或垂直地在X或Y轴上移动,他们从来不走对角线。每移动到一个新的方格算作一步(包括移出迷宫的那一步)这是一个W=5,H=3的迷宫:
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+
如上图的例子,栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。
格式
PROGRAM NAME: maze1
INPUT FORMAT:
(file maze1.in)
第一行: W和H(用空格隔开)
第二行至第2*H+1行: 每行2*W+1个字符表示迷宫
OUTPUT FORMAT:
(file maze1.out)
输出一个单独的整数,表示能保证牛从迷宫中任意一点走出迷宫的最小步数。
SAMPLE INPUT
5 3
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+
SAMPLE OUTPUT
9
=========================== 华丽的分割线===========================
这一题看网上都说用Flood Fill,, 我感觉的话应该用广搜, 其实仔细想一想, 这一题的广搜等于Flood Fill.
我的思想是, 用广搜, visited[101][40]判重, 从两个起点开始搜索, 这两个点的初始值为1(就是说一步就能到终点). 每搜索到一个就把相应的visited中的值设置为1, 并且把并且把下一个的值加一(在自己的值上)..
代码写好了之后就是不能AC, 提示内存溢出,, 查了好久好久.. 才发现定义变量的时候错了,, 本来我是定义的: visited[40][101], 那么当i > 40的时候就可能溢出!!
大家注意下吧..
代码:
Overfencing
Kolstad and Schrijvers
Farmer John went crazy and created a huge maze of fences out in a field. Happily, he left out two fence segments on the edges, and thus created two "exits" for the maze. Even more happily, the maze he created by this overfencing experience is a `perfect' maze: you can find a way out of the maze from any point inside it.
Given W (1 <= W <= 38), the width of the maze; H (1 <= H <= 100), the height of the maze; 2*H+1 lines with width 2*W+1 characters that represent the maze in a format like that shown later - then calculate the number of steps required to exit the maze from the `worst' point in the maze (the point that is `farther' from either exit even when walking optimally to the closest exit). Of course, cows walk only parallel or perpendicular to the x-y axes; they do not walk on a diagonal. Each move to a new square counts as a single unit of distance (including the move "out" of the maze.
Here's what one particular W=5, H=3 maze looks like:
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+
Fenceposts appear only in odd numbered rows and and odd numbered columns (as in the example). The format should be obvious and self explanatory. Each maze has exactly two blank walls on the outside for exiting.
PROGRAM NAME: maze1
INPUT FORMAT
Line 1: W and H, space separated
Lines 2 through 2*H+2: 2*W+1 characters that represent the maze
SAMPLE INPUT (file maze1.in)
5 3
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+
OUTPUT FORMAT
A single integer on a single output line. The integer specifies the minimal number of steps that guarantee a cow can exit the maze from any possible point inside the maze.
SAMPLE OUTPUT (file maze1.out)
9
The lower left-hand corner is *nine* steps from the closest exit.
描述
农夫John在外面的田野上搭建了一个巨大的用栅栏围成的迷宫。幸运的是,他在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是,他所建造的迷宫是一个“完美的”迷宫:即你能从迷宫中的任意一点找到一条走出迷宫的路。给定迷宫的宽W(1<=W<=38)及长H(1<=H<=100)。 2*H+1行,每行2*W+1的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数(就是从最“糟糕”的一点,走出迷宫的最少步数)。(即使从这一点以最优的方式走向最靠近的出口,它仍然需要最多的步数)当然了,牛们只会水平或垂直地在X或Y轴上移动,他们从来不走对角线。每移动到一个新的方格算作一步(包括移出迷宫的那一步)这是一个W=5,H=3的迷宫:
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+
如上图的例子,栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。
格式
PROGRAM NAME: maze1
INPUT FORMAT:
(file maze1.in)
第一行: W和H(用空格隔开)
第二行至第2*H+1行: 每行2*W+1个字符表示迷宫
OUTPUT FORMAT:
(file maze1.out)
输出一个单独的整数,表示能保证牛从迷宫中任意一点走出迷宫的最小步数。
SAMPLE INPUT
5 3
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+
SAMPLE OUTPUT
9
=========================== 华丽的分割线===========================
这一题看网上都说用Flood Fill,, 我感觉的话应该用广搜, 其实仔细想一想, 这一题的广搜等于Flood Fill.
我的思想是, 用广搜, visited[101][40]判重, 从两个起点开始搜索, 这两个点的初始值为1(就是说一步就能到终点). 每搜索到一个就把相应的visited中的值设置为1, 并且把并且把下一个的值加一(在自己的值上)..
代码写好了之后就是不能AC, 提示内存溢出,, 查了好久好久.. 才发现定义变量的时候错了,, 本来我是定义的: visited[40][101], 那么当i > 40的时候就可能溢出!!
大家注意下吧..
代码:
/* LANG: C ID: zqy11001 PROG: maze1 */ #include <stdio.h> #include <string.h> #define getint(i) scanf("%d", &i) #define MAX 1000 #define left 1 #define right 2 #define up 4 #define down 8 #define isempty() (tail == head) #define add(i, a, b) if(map[t.x][t.y] & i){\ en(a, b, t.t + 1);\ } struct node{ int x, y; int t; }queue[MAX]; int head, tail; int visited[101][40]; int map[101][40]; int w, h; void en(int i, int j, int n) { if(tail == (head + 1)%MAX){ exit(-1); } if(i < 1 || i > h || j < 1 || j > w){ return; } if(visited[i][j]){ return; } visited[i][j] = 1; queue[head] = (struct node){i, j, n}; head = (head + 1) % MAX; } void out(struct node *n) { if(tail == head){ exit(-1); } *n = queue[tail]; tail = (tail + 1)%MAX; } int main(void) { int i, j, ch; int max = 0; struct node t; freopen("maze1.in", "r", stdin); freopen("maze1.out", "w", stdout); getint(w); getint(h); for(i = 1; i <= h; i++){ for(j = 1; j <= w; j++){ map[i][j] = 15; } } for(i = 1; i <= 2 * h + 1; i++){ getchar(); for(j = 1; j <= 2 * w + 1; j++){ ch = getchar(); if((i == 1 || i == 2*h+1) && ch == ' '){ en((i + 1) / 2, j / 2, 1); en(i / 2, j / 2, 1); } if((j == 1 || j == 2*w+1) && ch == ' '){ en(i / 2, (j + 1)/2, 1); en(i / 2, j / 2, 1); } if(strchr(" +", ch) != NULL){ continue; } if(i & 1){ map[(i + 1)/2][j/2] -= up; map[i / 2][j / 2] -= down; }else{ map[i/2][(j+1)/2] -= left; map[i/2][j/2] -= right; } } } while(!isempty()){ out(&t); add(left, t.x, t.y - 1); add(right, t.x, t.y + 1); add(up, t.x - 1, t.y); add(down, t.x + 1, t.y); if(max < t.t){ max = t.t; } } printf("%d\n", max); return 0; }
发表评论
-
重做 USACO 1.1 黑色星期五
2010-03-31 18:59 1265/* LANG: C ID: zqynux11 PROG ... -
重做 USACO 1.1 黑色星期五
2010-03-31 18:59 807解释什么的就算了吧,, /* LANG: C ID: ... -
重做 USACO 1.1 贪婪的送礼者
2010-03-31 18:58 1208这题的话, 我用的是个结构体, 记录各个人.. 我错了的地 ... -
重做 USACO 1.1 你的飞碟在这儿
2010-03-31 18:56 850不解释了.. /* LANG: C ID: zqynu ... -
USACO 3.1 Shaping Regions 形成的区域
2010-03-30 20:01 1496这题二话不说, 用map[i][j]表示坐标为i, j的点 ... -
USACO 3.1 Humble Numbers 丑数
2010-03-28 15:31 1441从这一题开始,, 以后题目我就不贴上来了... 自己去看吧 ... -
USACO 3.1 Score Inflation 总分
2010-03-27 20:19 802Score Inflation The more point ... -
USA 3.1 Agri-Net 最短网络
2010-03-27 20:14 842Agri-Net Russ Cox Farmer John ... -
USACO 2.4 Fractions to Decimals 分数化小数
2010-03-27 15:47 1247Fractions to Decimals Write a ... -
USACO 2.4 Bessie Come Home 回家
2010-03-27 13:01 994Bessie Come Home Kolstad & ... -
USACO 2.4 Cow Tours 牛的旅行
2010-03-27 11:57 1079Cow Tours Farmer John has a nu ... -
USACO 2.4 The Tamworth Two 两只塔姆沃斯牛
2010-03-23 22:05 1169The Tamworth Two BIO '98 - Rich ... -
USACO 2.3 Controlling Companies 控制公司
2010-03-23 22:00 1417Controlling Companies Some com ... -
USACO 1.1 Broken Necklace 破碎的项链
2010-03-22 18:04 2074Broken Necklace You have a neck ... -
USACO 2.3 Money Systems 货币系统
2010-03-22 13:31 949Money Systems The cows have no ... -
USACO 2.3 Cow Pedigrees 奶牛家谱
2010-03-21 15:02 1408Farmer John is considering purc ... -
USACO 2.3 Zero Sum 零的算式和
2010-03-20 14:30 1757Zero Sum Consider the sequence ... -
USACO Longest Prefix最长前缀
2010-03-17 12:28 1399Longest Prefix IOI'96 The stru ... -
vijos 谁拿了最多奖学金
2010-03-17 12:25 1064描述 Description 某校的惯例是在每 ... -
USACO 2.2 Subset Sums集合
2010-03-16 12:18 1422USACO 2.2 Subset Sums集合 For ...
相关推荐
usaco2.4解题报告1
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
usaco历年测试数据
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
USACO题集及答案
某些USACO题目的答案,很详细,代码清晰结构良好,算法高效易于调试
usaco的总结和心得 包括了对题目的分了和总结 以及对题目的解法概括
USACO历年比赛测试数据:2003年 方便大家测试
内含USACO全部测试数据,绝对全
USACO做题代码
USACO教程,包含USACO全部英文原题,题解(NOCOW整理版),翻译,教程,代码,测试数据。
USACO全部译题 USACO Training Program Gateway
USACO1.1的源代码,新手入门可用 Only post for the new c++ students
usaco traning的全部数据 才要3分
USACO所有题目的题解 NOCOW整理版
USACO历年比赛测试数据:2006年方便大家测试
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
含2001~2017全部比赛赛题测试数据 2001~2007 数据√ 题面× 标程题解× 2008~2010 数据√ 题面√ 标程题解× 2011~2017 数据√ 题面√ 标程题解√ 其中除2008~2010外其他年份均按照年度、月度、金银铜白金组别整理...
Usaco总结&题解 一位大牛写的Usaco的总结,并有所有题的题解,推荐!!
数据结构机考所参考的USACO网站所有题目的解题思路,资源比较稀有!