Problema C - Planeta Arrakis

Estamos no ano de 10191. O Universo é dominado pelo Imperador Shaddam IV, num ambiente complexo, com influência de várias casas, várias raças, com todos a conspirarem uns contra os outros. E nesta altura, a substância mais importante de todo o universo é a spice melange (especiaria), que aumenta a longevidade humana e expande a consciência. Esta substância apenas existe num único sítio, no planeta Arrakis (também conhecido simplesmente como Dune), um planeta completamente desértico, sem uma única gota de chuva, habitado pelos Fremen, um povo que vive escondido em grutas no meio do deserto, com os olhos completamente azuis devido à saturação de especiaria. Para além deles, existem os temíveis e gigantescos vermes do deserto, adorados pelos Fremen como Shai Hulud, que são atraídos pelas vibrações rítmicas, destruindo tudo à sua passagem.

Apanhar especiaria no deserto profundo (onde ela se encontra em maior quantidade) é uma tarefa difícil e complicada, que é levada a cabo por harvesters, veículos de recolha de especiaria, com a ajuda de carryals, veículos aéreos que transportam os harvesters. O que fazem é plantar um thumper, um objecto que provoca vibrações, servindo de falso isco para os vermes, e enquanto isso apanham o máximo de especiaria, antes que o verme venha ter com eles.

A tua tarefa é ajudá-los na recolha de especiaria. Podes supor que o thumper já foi colocado e tens de descobrir, dado um mapa, qual o máximo de especiaria que é possível apanhar. Para simplificar o mapa é descrito como uma matriz. O harvester começa sempre no topo do mapa (linha de cima) e o carryal está sempre na linha de baixo. O harvester só pode deslocar-se para baixo, para a esquerda, ou para a direita, e depois de começar a andar numa linha, apenas pode deslocar-se no mesmo sentido (isto é, por exemplo, se começar a andar para a direita, não pode andar para a esquerda na mesma linha). É que o medo de ser comido por um verme é enorme, e como o thumper foi plantado no topo, interessa "fugir" do verme e aproximar-se do carryal, para voar para fora da zona com a especiaria apanhada.

Dado um mapa, quanta especiaria é possível apanhar? Supões que uma quadrícula de especiaria corresponde a 1, e que o harvester, ao passar por uma casa com especiaria, consegue recolhê-la. Existem também algumas zonas rochosas, onde o harvester não consegue passar.

O Problema

Input

Na primeira linha de input vêm dois números inteiros, LIN e COL, que representam respectivamente o número de linhas e de colunas do mapa a considerar (1 ≤ LIN,COL ≤ 500). Seguem-se LIN linhas, cada uma contendo exactamente COL caracteres, indicando o conteúdo do mapa:

• '.' representa a areia, uma casa sem nada no meio do deserto
• 'S' representa uma quadrícula de especiaria
• '#' representa uma zona rochosa, na qual o harvester não consegue passar
• 'H' representa o harvester (está sempre na primeira linha)
• 'C' representa o carryal (está sempre na última linha)

Podes assumir que no input existe sempre apenas um 'H' e apenas um 'C', para além de um número qualquer de '.', 'S' e '#'.

Output

O output é constituído por uma única linha, contendo um número inteiro que corresponde à quantidade de especiaria que é possível apanhar, de modo a começar onde o harvester está e terminar no carryal.

Podes assumir que é sempre possível chegar do ponto inicial ao ponto final, o do carryal.

Exemplo de Input 1

3 5
S.H.S
S#...
..#.C

Exemplo de Output 1

1

Exemplo de Input 2

4 6
S..H.S
.###.S
.SS...
C.SS..

Exemplo de Output 2

5