Længeste rute fra A til B

Hej,

Jeg har siddet og arbejdet med de forskellige algoritmer for at finde den hurtigste vej fra A til B. Nu vil jeg gerne gøre det omvendt. - Til at genere den hurtigste vej i mit program har jeg valgt at bruge A*.

Nå men idéen med dette er at kunne spille tower defence maps automatisk. Men det kræver selvfølgelig at man kan bygge den "perfekte" maze.

Jeg tager udgangs punkt i de 2 baner i starcraft 2 ved navn "Random TD" og "Split TD", da det er baner med åbne fields hvor vejen ikke er bestemt på forhånd, da de maps er en del nemmere at genere en maze til.

Til at starte med får man et field lad os sige det er 10x10
hvor man kan bygge (I det rigtige spil vil der også være walls rund omkring på mappet, det starter jeg med at se bort fra)

XXXXXXXXXXXX
XE.........X
X..........X
X..........X
X..........X
X..........X
X..........X
X..........X
X..........X
X......S...X
X..........X
XXXXXXXXXXXX

. = path
X = wall
s = start
e = end

Det gælder nu om at genere den længst mulige vej ved at placere tårne rundt på mappet. - Jeg kan desværre ikke rigtig finde ud af hvilken algoritme der kan bruges til dette.

Min næste problem er så at der også er at maksimal antal tårne man kan placere, hvilket igen gør det endnu svære :)

Jeg har ikke tænkt mig at bruteforce problemet, da det ikke vil være en mulighed hvis mappet går hen og bliver 100x100 - Dog er dette ikke tilfældet ville bare give et eksempel.

Det med at der er et maksimal antal tårne behøver algoritmen ikke at understøtte, det skal jeg nok selv prøve at udvide bagefter. :) - Men håber der er nogen der kender til en algoritme eller har prøvet løse det selv, der kan hjælpe mig videre så jeg ikke ender med at lave bruteforce :D

Normalt programmere jeg i C# - Men hvis nogen skulle have kode eksempler vil jeg meget gerne se dem :)