Task Authors: Monika Steinová (CHE/SWK), Michal Forišek (SWK)

This is known to be a hard problem. No general polynomial algorithm is known for this problem, that is, no algorithm has been discovered that is guaranteed to solve each problem instance in a time polynomial in the size of the problem (area of the corn field).

This is also the reason why this task was offered as an output-only task, where the contestants were given 10 specific instances (corn fields) to tackle. They could do this by hand, or write programs to analyze these mazes, and write yet other programs (potentially, a different program for each field) to produce a long(est) path. Note that the path need not be optimal; points could also be scored for (good) approximations.

Here are some characteristics and results by Tor Myklebust (HSC member) for the 10 instances that the contestants had to tackle:

	Characteristics		Tor's result
Instance	Dimensions	Obstructions	Path length	Score
1	10x10	8	20	10.00
2	100x100	1766	4026	10.15
3	100x100	3216	3740	8.61
4	100x100	2283	3733	8.58
5	100x100	1357	4738	8.86
6	11x11	0	54	10.00
7	20x20	210	33	10.00
8	20x20	122	95	10.00
9	11x21	10	106	10.45
10	200x200	15224	7506	9.17
Total				95.82