October 16th - Mud Path Problem, Mine Field Problem

Go down

October 16th - Mud Path Problem, Mine Field Problem

Post  Dan on Thu Oct 16, 2008 11:14 pm

Mud Path Problem

In front of you there is a path of squares and a bundle of wooden planks. Each square either contains a patch of grass or mud. You want to cover all of the patches of mud so people can walk across without getting dirty while minimizing the amount of grass patches covered by the planks (if grass is covered by a plank it won’t get any sun and will die). Your task is to cover all the patches of mud while minimizing the number of grass patches you cover. Given the maximum number of planks you can use (each plank can be any size you want it to be) (1<=M<=50), the number of squares the path has (0<=N<=200), the number of patches of mud (1<=P<=N), and a list of all of the positions of the patches of mud (1<=A<=N), find the minimum number of path squares that need to be covered in order to cover all of the patches of mud.

M N P
A
B
C
D


Use any form of input and output you want.


Challenge: Minefield Problem
Given the length of a square minefield (0<=L<=50), the maximum number of fence squares you can use (1<=M<=20) (fence squares can have any length and widths), the number of mines on the minefield (1<=N<=L*L), followed by the x y coordinates of the N mines (separated by a space), find the smallest possible number of squares that need to be fenced in on the minefield while making sure that all of the mines are fenced in.

L, M, N
x1 y1
x2 y2
x3 y3


avatar
Dan
Alumni
Alumni

Number of posts : 73
Age : 27
Location : Waterloo, Ontario
Grade : >12
L337ness :
69 / 10069 / 100

Registration date : 2008-08-27

View user profile

Back to top Go down

Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum