Solution en Haskell

300ms pour la partie 2.

Pour la partie 1, il faut remarquer vu que la parité de la distance au point de départ change à chaque déplacement. La distance entre le point de départ et un sommet accessible après 64 mouvements est donc toujours pair.

Du coup, les sommets à trouver sont ceux situés exactement à distance n où n est pair et n <= 64.
Un simple parcours en largeur fait l'affaire.

Pour la partie 2, ça se complique.
Mais on repère que l'instance est assez particulière:
- la grille de départ est carrée;
- le point de départ se trouve au centre;
- la ligne horizontale, la ligne verticale ainsi que les diagonales autour du centre sont vides.

Notons f(n) le nombre de points accessibles après n mouvements et notons M la taille (verticale et horizontale) de la grille.
On peut donc se dire qu'il doit y avoir une régularité entre f(n) et f(n+M).

Notons r = 26501365 mod M et regardons la suite des u_i = f(r + iM) pour i entier naturel.
Après avoir calculé les 5 ou 6 premières valeurs par ordinateur, on se rend compte que la suite est une séquence quadratique ou dit autrement que la suite des dérivées discrètes secondes est constante. Elle est donc de la forme u_n = a *n^2 + b * n + c.
Il faut donc calculer u_n avec n = 26501365 // M où // désigne la division entière.

Pour calculer u_n, on a besoin que des 3 premiers termes de la suite.
Notons d1 = u1 - u0, d2 = u2 - u1 et d' = d2 - d1 alors
u_n = u0 + n * d1 + n * (n-1) * d' / 2.
Et voilà !

Voici le code un peu commenté.

Tout d'abord le parsing et un précalcul pour transformer l'entrée en matrice et repérer le sommet de départ.

data Tile = Garden | Rock | Start deriving (Eq)
type Grid = Matrix U Bool
parser :: Parser [[Tile]]
parser = some tile `sepEndBy1` eol where
 tile = Garden <$ "." <|> Rock <$ "#" <|> Start <$ "S"
precomp :: [[Tile]] -> Maybe (Grid, V2 Int)
precomp tiles = do
 start <- listToMaybe [V2 i j | (i, j, Start) <- flattenWithIndex tiles]
 let tiles' = map (map (==Rock)) tiles
 let matrix = fromLists' Seq tiles'
 pure (matrix, start)

Pour la partie 1, on définir une fonction nbors qui donne le voisinage d'une tuile.
Comme on ne sort pas de la grille dans la partie 1 et pour factoriser avec la partie 2,
on fait des modulo sur les coordonnées.

nbors :: Grid -> V2 Int -> [V2 Int]
nbors grid = filter (not . (grid !) . toIx2 . mod2) . adjacent where 
 Sz2 h w = size grid
 mod2 (V2 r c) = V2 (r `mod` h) (c `mod` w)
part1 :: (Grid, V2 Int) -> Int
part1 (grid, start) = count even . takeWhile (<=64) . map fst $ bfs (nbors grid) start

Pour la partie 2, on définit d'abord une fonction générique pour calculer le n-ième d'une séquence quadratique.

-- given a quadratic sequence with first terms u0, u1, u0, compute u_n
quadraticSequence :: Integer -> Integer -> Integer -> Integer -> Integer
quadraticSequence u0 u1 u2 n = u0 + n * d1 + n * (n-1) * d' `div` 2
 where
 d1 = u1 - u0
 d2 = u2 - u1
 d' = d2 - d1

Ensuite, on peut l'appliquer à notre problème en calculant les trois premiers termes de la suite grâce à un parcours en largeur.

part2 :: (Grid, V2 Int) -> Integer
part2 (grid, start) = result where
 nbSteps = 26_501_365
 Sz2 h _ = size grid
 r = nbSteps `mod` h
 bfsTrace = map fst $ bfs (nbors grid) start
 countParity x = fromIntegral . count (\y -> even (y - x)) 
 nbReachable x = countParity x $ takeWhile (<=x) bfsTrace
 u0 = nbReachable r
 u1 = nbReachable (r+h)
 u2 = nbReachable (r+2*h)
 result = quadraticSequence u0 u1 u2 (fromIntegral $ nbSteps `div` h)