2153 - じゃんけんカーペット(Rock-Scissors-Paper Carpet))

問題

オシャレ好きのビ太郎は、カーペットを新調した。カーペットは縦$H$行、横$W$列のマス目状に区切られた長方形の形をしており、各マスには「グー」「チョキ」「パー」のいずれかの模様が描かれている。カーペットの上から$i$行目、左から$j$列目$(1 \leq i \leq H , 1 \leq j \leq W)$にあるマスに描かれている模様は、文字列$S_i$の$j$文字目が$G$のとき「グー」、$C$のとき「チョキ」、$P$のとき「パー」である。 ビ太郎は、カーペットの最も左上のマスに駒を置き、以下の操作を何回か行うことで、その駒をカーペットの最も右下のマスに到達させるという遊びを思いついた。

・駒が置かれているマスの上下左右に隣接するマスを1つ選び、そのマスに駒を移動させる。
　このとき、以下のルールで移動にコストがかかる。

　・駒の移動前のマスに描かれているじゃんけんの手が、駒の移動後のマスに描かれている
　　じゃんけんの手に対して勝っている場合、コストはかからない。
　・駒の移動前のマスに描かれているじゃんけんの手が、駒の移動後のマスに描かれている
　　じゃんけんの手に対してあいこである場合、コスト1がかかる。
　・駒の移動前のマスに描かれているじゃんけんの手が、駒の移動後のマスに描かれている
　　じゃんけんの手に対して負けている場合、コスト2がかかる。

ビ太郎は、かかるコストをなるべく少なくしたい。
カーペットの模様の情報が与えられたとき、操作を繰り返すことで左上のマスから右下のマスに駒を到達させるためにかかるコストの最小値を求めるプログラムを作成せよ。

制約

• $1 \leq H \leq 500$
• $1 \leq W \leq 500$
• $(H,W)≠(1,1)$
• $S_i$は長さ$W$の文字列である$(1 \leq i \leq H)$。
• $S_i$の各文字は$G$、$C$、$P$のいずれかである$(1 \leq i \leq H)$。
• $H,W$は整数である。

小課題

• 1.(8点)$H=1$
• 2.(24点)$H=2$
• 3.(68点)追加の制約はない

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$
$S_1$
$S_2$
...
$S_H$

出力

操作を繰り返すことで左上のマスから右下のマスに駒を到達させるためにかかるコストの最小値を出力せよ。 出力の最後に改行を入れること。

入出力例

入力例1

1 4
GCCG

出力例1

3

まず、駒をマス(1,1)から(1,2)へ動かす。このとき、じゃんけんで「グー」は「チョキ」に勝っているため、コストはかからない。
次に、駒をマス(1,2)から(1,3)へ動かす。このとき、じゃんけんで「チョキ」と「チョキ」はあいこなため、コスト1がかかる。
最後に、駒をマス(1,3)から(1,4)へ動かす。このとき、じゃんけんで「チョキ」は「グー」に負けているため、コスト2がかかる。
0+1+2=3より、合計でコスト3がかかる。かかるコストを3未満にすることは不可能なので、3を出力する。
この入力例は小課題$1,3$の制約を満たす。

入力例2

2 5
GPGGP
CGCCP

出力例2

3

この入力例は小課題$2,3$の制約を満たす。

入力例3

6 4
PCGP
CCGC
PGPC
PPGP
CGCP
PGGP

出力例3

5

この入力例は小課題$3$の制約を満たす。

入力例3

3 7
PGPCGCG
GPPCPGP
CCCGCCG

出力例3

6

この入力例は小課題$3$の制約を満たす。