October 16th - Mud Path Problem, Mine Field Problem

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
…