Editorial for 2015 ACM Course Practice Contest 1

The topic of this contest is Brute Force Searching techniques including Depth-First-Searching and Breadth-First-Searching.

The problems are ALL selected by Guo Yu (Union Class) from PKU Online Judge.The dataset and problem description are altered and translated by him.

I assessed the difficulty of these problems,implemented the solutions and wrote this editorial.Should you have any question,  please feel free to leave a comment on this post.Thanks!

If you want to practice these problems after the match, please visit ACMコース1〜DFSとBFS.

For test datasets, altered problem descriptions, and standard implementation provided by original contest holder,please check this archive ACM Course 1 .

A 迷宫还是三维的好

Problem Description

hahaschool误入了一个三维迷宫,他需要尽快离开迷宫,回宿舍打osu.他只可以上下左右移动,不能跨过障碍物,请你帮他算出他走出迷宫所需的最短距离.

输入包含多组,每组数据第一行包含三个整数数H,L,W (均不超过30)分别表示迷宫的高,长,宽.
接下来依次输入0,到H – 1层的俯视图.每层俯视图包括L行,每行W个字符.
最后一组输入为0 0 0,不需处理.
图例:
S:起点(有且仅有一个)
E:终点(有且仅有一个)
#:障碍物
. : 路
每组数据输出一个整数表示最少的步数,如果不能到达终点,请输出一行osu!以表遗憾

Original Problem

POJ 2251

Difficulty

BASIC

Key Point

Breadth-First-Searching

Tutorial

Click the following link to read:

POJ 2251 Dungeon Master

B 门前大桥下,游过一群鸭

Problem Description

“门前大桥下,游过一群鸭,快来快来数一数,二四六七八”你唱出来了对不对~
由于这首歌流传较广,一唱起来便觉得这时间再无鸭可数,也便没了兴致.
于是你开始数江,河,湖,海,水塘,浴缸,下水道……总之一切能数的水体,都要数个遍!
给出水域分布图,需要你数共有多少个两两不相连的水域.其中一个或多个相连的水体被认为是一个水域.(当且仅当格子间有一条公共边,才认为两格子相连)

输入
输入包含多组数据
第一行N,M(均不超过100)表示地图的尺寸(N*M)
接下来N行表示地图
图例:
. :陆地
W :水体

输出
输出一个非负整数,表示水域的个数

Original Problem

POJ 2386

Difficulty

BASIC

Key Point

Depth-First-Searching

Tutorial

Click the following link to read:

POJ 2386 Lake Counting

C 不扶不行

Problem Description

众所周知,yinz是一位德高望重的老爷爷.但是由于上了年纪,走路只能扶墙.为了锻炼身体,他来到了一个迷宫,机智的yinz看着迷宫的地图,开始思考扶着哪面墙走能最快到达终点,请你帮助他.yinz只可能向前后左右四个方向移动.

第一行输入一个整数 T(T<10)表示数据组数.
接下来T组数据,每组数据第一行包含两个整数数L,W (3 <= L, W <= 40)分别表示迷宫的长,宽.接下来L行,输入迷宫的地图.
图例:
S:起点(有且仅有一个)
E:终点(有且仅有一个)
#:障碍物
. : 路

每组数据输出一个整数表示最少的步数,为了表示对老年人的尊重,数据保证能够到达终点.

Original

POJ 3083

Difficulty

ADVANCED

Key Point

Breadth-First-Searching,Manipulating Directional Vectors

Tutorial

Click the following link to read:

POJ 3083 Children of the Candy Corn

D 卡牌大师

Problem Description

欢迎来到召唤师峡谷,作为一名成熟的召唤师,你拥有许多各色各样的英雄.他们是卡牌大师,卡牌大师,卡牌大师….还有卡牌大师.现在,你要做的不是中单,而是洗牌.
你洗牌的手法很娴熟,左手右手一个慢动作,一看就是新东方出来的.新东方洗牌的动作是这样的,
开始有两堆数量相等的卡牌S1,S2你需要轮流用两堆的卡牌插入,如下图所示

洗牌
当然这仅仅是第一轮,如果对牌序还是不满意,你会将这堆牌上下等分(上面的部分为S1余下的为S2)重复上面的操作,直到满意为止.
你突然好奇,要多少次轮才能得到你满意的牌序.

输入
第一行输入一个正整数N (1 ≤ N ≤ 1000),表示有N组数据
每组数据第一行输入一个正整数C(1 ≤ C ≤ 100),表示S1堆的牌数(S2的与S1相等).接下来的两行,输入两行字符串,分别表示S1和S2,其中不同的字符表示不同的牌.最后输入目标牌序.

输出
每组数据输出两个正整数,分别表示对应第几组数据,第一次获得目标牌序的洗牌次数(如果不能获得则输出-1)

Original Problem

POJ 3087

Difficulty

BASIC

Key Point

Simulation,Brute Force

Tutorial

Click the following link to read:

POJ 3087 Shuffle’m Up

E 素数们

Problem Description

素数们人口比较稀疏,要知道除了2和3相邻外,其他的素数可没那么好运气.他们每次互相拜访都会花费大量的时间来寻找.但是现在好了,素数们有特殊的”快捷通道”.比如1033要去拜访8179,他可以每次只改动某一位数,到达其他素数,最终到达8179只需要6步(1033->1733->3733->3739->3779->8779->8179).现在这种”快捷通道”已经推广了,有很多素数迫不及待的准备拜访他的朋友,请你帮助他们算出使用”快捷通道”最少需要多少步才能见到他们的朋友

输入:第一行一个正整数T表示输入数据组数(不超过100组)
每组数据包含两个四位素数a,b (不存在0002,0017,0107等输入)
输出:
对于每组数据输出最少步数.

Tips:
素数判断可以用埃式筛法预处理O(n),之后O(1)查询.

Original Problem

POJ 3126

Difficulty

BASIC(Assuming you can implement the sieve of Eratosthenes)

Key Point

Sieve of Eratosthenes,Breadth-First-Searching

Tutorial

Click the following link to read:

POJ 3126 Prime Path

F 寻宝

Problem Description

你是一名勇士,名叫ZhuRenGong.今天收到消息,沉寂多年的宝物DaBaojian又重现江湖,为了避免一场腥风血雨,时间紧迫,必须尽快赶到,夺取DaBaojian.
你有三种移动方式,假设你所在的位置为x,你可以走到x-1,x+1,或者瞬移到2*x.那么,拯救苍生的任务就交给你了,勇士.

输入
多组数据,处理到文件结束.
每组数据包括两个正整数N(0 ≤ N ≤ 100,000),K(0 ≤ K ≤ 100,000)

输出
请输出最少的步数

Original Problem

POJ 3278

Difficulty

ADVANCED

Key Point

Breadth-First-Searching with some optimisation techniques

Tutorial

Click the following link to read:

POJ 3278 Catch That Cow

Leave a Reply

Scroll to top